- #1

scorpius1782

- 107

- 0

## 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!

Last edited: