1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Recursion Tree

  1. Mar 31, 2014 #1
    1. The problem statement, all variables and given/known data
    Let the function t(n) be defined recursively by:

    ##t(1) = 1##
    ##t(n) = 3t(\frac{n}{2}) + n + 1## for n a power of two greater than 1.

    Draw several levels of the recursion tree for t, and answer the following:

    What will the height of the tree be if n is a power of 2?

    And what is the sum of values on level 3. assume ##n\geq 16##

    2. Relevant equations



    3. The attempt at a solution

    I did the tree where (n+1) is the root. Each successive level is ##\frac{n+1}{2^k}## with ##3^k## nodes at each height (height =k). So, from my lecture notes to get height I set ##\frac{n+1}{2^k}=1##. I'm sort of stuck here. I do not have the option (it is multiple choice) of ##k=log_2(n+1)## so I must have don't something wrong or I need to manipulate my answer in a way that isn't clear to me.

    For the sum of values I have 3^3 nodes each of value ##\frac{n+1}{2^3}## I thought that I could just say ##3^3\frac{n+1}{2^3}## but this is not an answer either. The closest possible answer was ##3^3n+3^3##

    Thanks for any help!
     
    Last edited: Apr 1, 2014
  2. jcsd
  3. Mar 31, 2014 #2

    Mark44

    Staff: Mentor

    I don't understand the line above.

    Did you mean this:
    ##t(n) = 3 t(\frac{n}{2}) + n + 1##
     
  4. Apr 1, 2014 #3
    Yes sorry, i fixed it. I pasted plain text and took them out for some reason.
     
  5. Apr 1, 2014 #4

    Mark44

    Staff: Mentor

    I would start playing with it. You're given t(1) = 1. What's t(2)? t(4)? And so on. I'm not sure what is meant by "recursion tree" other than how many times the formula will be used to evaluate t(n).
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Recursion Tree
  1. Binary trees (Replies: 1)

  2. Recursive function (Replies: 16)

  3. Parse tree (Replies: 3)

  4. Recursive calls (Replies: 15)

Loading...