основная теорема f (n) = nlogn

Question

Я работаю над проблемой 4-3 из введения в алгоритм, 3-е издание. И меня просят найти асимптотические верхнюю и нижнюю оценки для T (n):

T (n) = 4T (n / 3) + n lg (n)

Я нашел решение в Интернете, и решение говорит:

По теореме магистрата получаем T (n) ∈ Θ (n ^{log ₃ (4)} )

Я полагаю, что решение предполагает, что n ^{log ₃ 4} асимптотически больше, чем n lg (n)? Но почему это правда? Буду благодарен, если кто-нибудь поможет мне разобраться!

Answer 1

С точки зрения непрофессионала:

Нам нужно сравнить рост n*log(n) с n^1.25 (log3(4)~1.26)

Разделите обе функции на n

  log(n) vs n^(1/4)

Оба увеличиваются.
Производные обеих функций

  n^(-1)  vs n^(-3/4)  

Производная второго явно больше, поэтому вторая функция растет быстрее

Мы видим , что графики этих функций пересекаются, и степенная функция становится больше для больших значений n - для любой power>1