Вопрос о сложности времени и основной теореме

Question

Я довольно новичок в алгоритме, и я столкнулся с вопросом, что я не знаю, как применить основную теорему:

У нас есть алгоритм A, который решает P, создавая 3 подзадачи, каждая размером 2n/3, рекурсивно решая каждую подзадачу, а затем объединяя решения за O(nlogn) время. Будет ли этот алгоритм иметь лучшее время выполнения, чем O(n)? Докажите свой ответ.

Здесь я знаю a=3, b=3/2, но как мне справиться с O(nlogn)?

Answer 1

Henve, рекурсивная формула T(n) = 3T(2n/3) + O(n\log(n)). Как f(n) = O(n\log(n)) = O(n^{\log(3)/\log(1.5)}) ~ O(n^{2.7}), из основной теоремы мы можем сказать T(n) = \Theta(n^{2.7}). Следовательно, T(n) = \Omega(n^{2.7}).