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

Thread: recursion tree method to solve the recurrence

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

    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
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This a Codeguru.com survey!


HTML5 Development Center