What is the height of the recursion tree for t(n) when n is a power of 2?

[scorpius1782]

Homework Statement

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$

Homework Equations

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!

 

[Mark44]

Homework Statement

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.

I don't understand the line above.

Did you mean this:
$t(n) = 3 t(\frac{n}{2}) + n + 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$

Homework Equations

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!

 

[scorpius1782]

Yes sorry, i fixed it. I pasted plain text and took them out for some reason.

 

[Mark44]

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