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

Question

Я получил следующую рекурсию:

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

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

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

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

Answer 1

OK, чтобы ответить на ваш явный вопрос о том, почему n^(log_1.5(2)) является omega(n lg n): Для всех к> 1, п^к растет быстрее, чем 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)