- Thread starter
- #1

#### ATroelstein

##### New member

- Jun 30, 2012

- 15

$$

T(n) = 0, n = 1\\

T(n) = T(\frac{n-1}{2}) + 2C, n > 1

$$

Using a top-down approach to unrolling the equation to find the pattern, I get:

$$

T(n) = T(\frac{n-k}{2^{k}}) + 2kC

$$

Now I want to solve for k and associate it with n to finish solving the equation without k in it. In order to get:

$$

T(\frac{n-k}{2^{k}}) = T(1)

$$

Then:

$$

n-k = 2^{k}

$$

The problem I am running into is that I'm having trouble solving this for k. I have worked through many other examples where:

$$

n = 2^{k}

$$

and then I know:

$$

k = log_2 n

$$

But having the n-k is making it difficult for me to solve for k. Thanks in advance.