Solve the recurrence $T(n) = 2 T(n/2) + 2$

Question

T(2) = 1 
T(1) = 0

Ans is (3/2)* n - 2

My solution is :

T(n) = 2 T(n/2) + 2
T(n) = 4 T(n/4) + 4
T(n) = 8 T(n/8) + 6
T(n)=(2^k)T(n/2^k) + 2k  
where k = log(n) ..... in base 2
as n/(2^k) = 1 for T(1)

I don't how to solve this type of question to get in terms of n only. Can anyone help me out?

Answer 1

I am a bit confused because as pointed out in the comments, the intial conditions don't exactly make sense. However, just taking T(2) = 1, we can obtain our result:

Since, $T(n) = 2*T(n/2) + 2 => T(n) = 2*(2*T(n/4) + 2) + 2 => T(n) = 2^2*T(n/2^2) + 2^2 + 2$

Proceeding further we get $T(n) = 2^2 * (2*T(n/2^3)+2) + 2^2 + 2 => T(n) = 2^3*T(n/2^3) + 2^3 + 2^2 + 2$

As you can see, the relation we get now is $T(n) = 2^k T(n/2^k) + 2 + 2^2 +...+2^k$

Now because I want to use the initial condition, let $n = 2^{k+1}$ Therefore, $T(n) = \frac{2^{k+1}}{2}T(\frac{2^{k+1}}{2^k}) + 2 + 2^2 +...+ 2^k$

Therefore, $T(n) = \frac{n}{2}T(2) + 2 + 2^2 +...+ 2^k$

Since, $2 + 2^2 +...+ 2^k$ is a geometric progression, using the formula for a geometric progression sum, we get $2 + 2^2 +..+2^k = \frac{2(1-2^k)}{1-2} = 2(2^k-1) = 2(\frac{n}{2} - 1)$

Using this result and the fact that T(2) = 1, we get $T(n) = \frac{n}{2}(1) + 2(\frac{n}{2}-1) = \frac{n}{2} + n - 2 = \frac{3n}{2} - 2$.

Answer 2

Hint.

Make $t_n = \log(a^n)+b$

so we have

$$ n\log a + b = 2\left(\frac n2\log a+ b\right)+2\to b = -2 $$

now assuming $t_2 = 2\log a - 2 = 1$ we have

$$ t_n = \frac {3n}{2} - 2 $$

Answer 3

T(n) = 2T(n/2) + 2 and T(n/2) = 2T(n/4) + 2 so if you put those together you get T(n) = 4T(n/4) + 6. Similarly T(n) = 8T(n/8) + 14.

You should stop the recursion one step sooner when argument to T is 2, since as noted in comment the recursion formula doesn’t hold from T(2) to T(1). To finish it, note that 2^(k-1) = n/2.

So, if n = 2^k after iterating k-1 times you get T(n) = 2^(k-1) T(n/2^(k-1)) + 2^k - 2 = n/2 T(2) + n - 2