Основная теорема с функцией nlogn

Question

Мы недавно получили задания в моем исследовании, чтобы решить сложность рекурсивных функций с помощью основной теоремы.Я знаю, что эти вопросы задавались здесь много, но я не могу найти ответ на этот вопрос из них.Один вопрос, в частности, хорошо описывает проблему: здесь

Моя проблема связана с рекурсивной функцией T(n) = 5*T(n/3) + n *log(n).Как указано в другом вопросе, это должно быть решено со вторым случаем (или неофициальным четвертым случаем, который довольно похож).Однако я не могу найти Биг-Тету f(n) = nlogn with a =5 and b = 3.

. Буду признателен за вашу помощь.

Answer 1

Задача может быть решена с помощью основной теоремы, если мы покажем, что f(n) = n log n = O(n^(log_3 5-\epsilon))

, если выполняется, то результат следует из первого случая основной теоремы

T(n) = Θ(n^(log_3 5))

Чтобы увидеть, что

• взять lim (n log n)/n^(log_3 5))
• оценить log_3 5 ~ = 1.4649 ..
• подстроить некоторыеepsilon = 0.0049 ...> 0,
• lim (n log n)/n^(1.46)
• отменить n
• limit log n / n^(0.45) = 0 и взять первый H'ospital
• limit n^(0.54)/(n * 0.46) =0