recursion tree and binary tree cost calculation
Posted
by Tony
on Stack Overflow
See other posts from Stack Overflow
or by Tony
Published on 2010-05-04T19:31:32Z
Indexed on
2010/05/04
19:38 UTC
Read the original article
Hit count: 309
algorithm
|computer-science
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)?
© Stack Overflow or respective owner
