recursion tree method to solve the recurrence
 CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

# Thread: recursion tree method to solve the recurrence

1. Junior Member
Join Date
Mar 2017
Posts
5

## 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
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 -> 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)).

Last edited by user4592357; March 12th, 2017 at 01: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
•

Click Here to Expand Forum to Full Width

This a Codeguru.com survey!