Recursion tree and binary tree cost calculation
I have the following recursion:
T(n) = T(n/3) + T(2n/3) + O(n)
The height of the tree will be log3 / 2 of 2. Now the recursion tree for this iteration is not a complete binary tree. It is missing nodes below. This makes sense to me, however I don't understand how the following little omega notation relates to the value of all leaves in the tree.
"... the total value of all leaves would then be Theta (n ^ log3 / 2 of 2), which, since log3 / 2 of 2 is a constant strictly greater than 1, is a small omega (n lg n)."
Can someone please help me understand how Theta(n^log3/2 of 2)
it becomes small omega(n lg n)
?
a source to share
OK to answer your explicit question about why n^(log_1.5(2))
there is omega(n lg n)
: For all k> 1, n ^ k grows faster than n lg n
. (Authorities are growing faster than magazines.) Therefore, since 2 > 1.5
, log_1.5(2) > 1
and therefore, is n^(log_1.5(2))
growing faster than n lg n
. And since our function is in Theta(n^(log_1.5(2)))
, it must also be inomega(n lg n)
a source to share