Найти формулу замкнутого конца для рекуррентного уравнения по основной теореме

Question

Можем ли мы решить это T(n) = 2T( n/2 ) + n lg n Основная теорема об уравнении рекуррентности Я исхожу из ссылки, где он заявляет, что мы не можем применить здесь основную теорему, потому что она не удовлетворяет ни одному из условий 3ree случая. С другой стороны, он взял еще один пример T(n) = 27T(n/3) + Θ(n^3 lg n) и найти закрытое решение theta(n^3logn) Для решения этого он использовал 2-й случай основной теоремы If f(n) = Θ(nlogba (lg n)k ) then T(n) ∈ Θ(nlogba (lg n)k+1) for some k >= 0 Здесь возникает путаница, почему мы не можем применить 2-й случай здесь, пока он полностью подходит для 2-го случая. Моя мысль: а = 2, б = 2; пусть k =1, тогда f(n) = тета (n^log_2 2 logn) для k =1, поэтому T(n) = тета (nlogn) Но, как уже упоминалось, мы не можем применить основную теорему.,

Примечание: это происходит из-за f(n) bcz в T(n) = 2T( n/2 ) + n lg nf(n) = nlog n И в T(n) = 27T(n/3) + Θ(n^3 lg n) * f(n) = theta(n^3log n) * Пожалуйста, поправьте меня, если я здесь не прав.

Answer 1

Используя случай 2 основной теоремы, я нахожу, что

 T(n) = Theta( n log^2 (n))

Ваша ссылка утверждает, что случай 2 theroem является:

 f(n) = Theta( n log_b(a))

В то время как из нескольких других ссылок, например, из мит, дело обстоит так:

 f(n) = Theta( n log_b(a) log_k(n)) for k >= 0