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

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?

• The conditions don't make sense. We have $$T(2)=2T(1)+2=2\neq1.$$ Jun 23, 2018 at 14:56
• @TheSimpliFire: The real is question cdn.geeksforgeeks.org/maximum-and-minimum-in-an-array So the condition is that. Jun 23, 2018 at 14:58
• If n is a power of 2, then we can write T(n) as: T(n) = 2T(n/2) + 2  After solving above recursion, we get T(n) = 3n/2 -2 Jun 23, 2018 at 14:59
• I am struck at this part. Jun 23, 2018 at 14:59

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

• Do let me know if there are any steps I need to clarify further! Jun 23, 2018 at 17:22
• It explains everything :) .Thanx Mr walia for explaining it . Jun 23, 2018 at 18:01

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$$

• I didn't get this one. Jun 23, 2018 at 17:57
• How did you reached to tn = (3/) * n - 2 ? Jun 23, 2018 at 17:59
• okay a = 2^(3/2) but how did u come up with log a^n - 2 ?? Jun 23, 2018 at 18:05
• The general solution for this type of difference equation is $t_n = \log(a^n)+b$ Substituting the general solution we can define the $b$ value and with the initial condition we fix the $a$ value. Is much like the procedure with the differential equation. Jun 23, 2018 at 19:14
• Thanx for the info :). Jun 24, 2018 at 3:35

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

• I know that .I was having problem in generalizing it in terms of n. Jun 23, 2018 at 17:56
• Edited to add the result after k-1 steps in terms of n. Hope that helps. Jun 23, 2018 at 18:14
• Thanx .It helps. Jun 24, 2018 at 3:35