расчет стоимости рекурсивного дерева и двоичного дерева

Question

У меня есть следующая рекурсия:

T(n) = T(n/3) + T(2n/3) + O(n)

Высота дерева будет log3 / 2 из 2. Теперь дерево рекурсии для этой рекурсии не является полным двоичным деревом.У него есть недостающие узлы внизу.Это имеет смысл для меня, однако я не понимаю, как следующая небольшая запись омега связана со стоимостью всех листьев в дереве.

"... общая стоимость всехтогда листья будут тэтой (n ^ log3 / 2 из 2), которая, поскольку log3 / 2 из 2 является константой, строго превышающей 1, является маленькой омега (n lg n). "

Может кто-нибудь помочь мне понять, как Theta(n^log3/2 of 2) становится small omega(n lg n)?

Answer 1

ОК, чтобы ответить на ваш явный вопрос о том, почему n^(log_1.5(2)) равно omega(n lg n): При всех k> 1 n ^ k растет быстрее, чем n lg n. (Полномочия растут быстрее, чем журналы в конце концов). Следовательно, поскольку 2 > 1.5, log_1.5(2) > 1 и, следовательно, n^(log_1.5(2)) растет быстрее, чем n lg n. И поскольку наша функция находится в Theta(n^(log_1.5(2))), она также должна быть в omega(n lg n)