Exploring t(n): Recursion Tree Analysis

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

 

[rezeew]

I would first like to clarify that recursion tree analysis is a method used to analyze the time complexity of recursive functions, where the height of the recursion tree represents the number of recursive calls made and the number of nodes at each level represents the number of operations performed at that level.

Now, let's look at the function t(n) given in the homework statement. If n is a power of 2, then we can write n as $2^k$ for some positive integer k. In this case, the recursion tree will have k levels, since each time the function is called, the input is halved. So, the height of the tree will be k, which is equal to log2(n).

To find the sum of values on level 3, we need to first determine the number of nodes at that level. Since the input is halved at each recursive call, the number of nodes at level 3 will be $\frac{n}{2^3} = \frac{n}{8}$. Now, each node at this level will have a value of $n+1$, so the sum of values on level 3 will be $\frac{n}{8}(n+1) = \frac{n^2+n}{8}$. Therefore, the correct answer would be $\frac{n^2+n}{8}$.