recursion tree and binary tree cost calculation
- by Tony
Hi all,
I've got the following recursion:
T(n) = T(n/3) + T(2n/3) + O(n)
The height of the tree would be log3/2 of 2. Now the recursion tree for this recurrence is not a complete binary tree. It has missing nodes lower down. This makes sense to me, however I don't understand how the following small omega notation relates to the cost of all leaves in the tree.
"... the total cost of all leaves would then be Theta (n^log3/2 of 2) which, since log3/2 of 2 is a constant strictly greater then 1, is small omega(n lg n)."
Can someone please help me understand how the Theta(n^log3/2 of 2) becomes small omega(n lg n)?