
March 12th, 2017, 12:16 PM
#1
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(n1) + 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: n1 > n2 and (n1)/2
right branch: n/21 and n/4
etc.
the tree isn't a complete binary tree, but we know that the longest path from root to leaf is the one from n > n1 > n2 > ... > 1 which is n levels. so the height if the tree is n.
calculating the costs at each level:
level 0: n
level 1: n1 + n/2 = 3/2n  1
level 2: (9n12)/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,...,n1
=> T(n) = sum(i=0,n1) (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"
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
This a Codeguru.com survey!
