March 12th, 2017, 12:16 PM
recursion tree method to solve the recurrence
i'm solving exercises from cormen's algorithms (3rd edition) using recursion tree but i'm stuck with this one: T(n) = T(n-1) + T(n/2) + n.
as usual, i first draw the tree (i drew the tree here but the formatting didn't show correctly so this is the "tree", ugh):
root: n -> n - 1 and n/2
left branch: n-1 -> n-2 and (n-1)/2
right branch: n/2-1 and n/4
the tree isn't a complete binary tree, but we know that the longest path from root to leaf is the one from n -> n-1 -> n-2 -> ... -> 1 which is n levels. so the height if the tree is n.
calculating the costs at each level:
level 0: n
level 1: n-1 + n/2 = 3/2n - 1
level 2: (9n-12)/4 = (3/2)^2 - 3
here we see a pattern: the cost of each level is (3/2)^i - b, for levels i = 0,1,2,...,n-1
=> T(n) = sum(i=0,n-1) (3/2)^i * n = n * [ (3/2)^n - 1 / (3/2) - 1 ] = 2n *[ (3/2)^n - 1 ] = 2n * (3/2)^n - 2n = O(n*(3/2)^n)?
i'm not sure that this is correct. is it? i've viewed a few other solutions on the internet but none of them even looks like this, one says it's O(n^2), the other - O(2^theta(logn)).
thanks in advance
Last edited by user4592357; March 12th, 2017 at 12:22 PM.
Reason: formatting didn't display the "tree"
Click Here to Expand Forum to Full Width
This a Codeguru.com survey!