arbre récursivité et le calcul binaire des coûts d'arbre

Question

J'ai la récursion suivante:

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

La hauteur de l'arbre serait LOG3/2 de 2. Maintenant, l'arbre de récursivité pour cette récurrence n'est pas un binaire complet arbre. Il a des nœuds manquants plus bas. Cela a du sens pour moi, mais je ne comprends pas comment la petite notation oméga suivante se rapporte au coût de toutes les feuilles dans l'arbre.

» ... le coût total de toutes les feuilles serait alors Theta (n^log3/2 de 2) qui, depuis log3/2 de 2 est strictement constant plus alors 1, est petit oméga (n lg n). "

Quelqu'un peut-il s'il vous plaît me aider à comprendre comment le Theta(n^log3/2 of 2) devient small omega(n lg n)?

Answer 1

OK, pour répondre à votre question explicite de savoir pourquoi n^(log_1.5(2)) est omega(n lg n): Pour tout k> 1, n^k croît plus vite que n lg n. (Les puissances croissent plus vite que les logs). Par conséquent depuis 2 > 1.5, log_1.5(2) > 1, et donc n^(log_1.5(2)) croît plus vite que n lg n. Et puisque notre fonction est dans Theta(n^(log_1.5(2))), il doit également être dans omega(n lg n)