## Interview Question

**Country:**India

T(n)=2T(n/2) + 2

T(n/2)=2T(n/4)+2

so T(n)=2(2T(n/4)+2)+2=4T(n/4) + 4+ 2

Similarly,T(n/4)=2T(n/8)+2

So T(n)=4(2T(n/8)+2)+4+2=8T(n/8)+8+4+2

hence,

T(n)=(2^k)T(n/2^k) +2^k + (2^k-1 )+ .. +2

You're missing the most important part: the conclusion. You need to say that you keep this recurrence going until you have T(1), so in your equality you want n / 2^k = 1, which implies n = 2^k or k = log base 2 of n. Substituting, you get T(n) = n *O(1) + n/2 +n4 +... = O(n) (by convergence of the sum of this series).

assume n = 2^K (2 per power K);

g(k) = 2 g(k-1) + 2;

2g(k-1) = 2^2g(k-1) + 2^2;

-- == -- + --

-- = -- + --

2^(n-1)g(2) = 2^n g(1) + 2^n

------------------------------------------

g(k) = 2^n g(1) + 2+ 2^2 + ...... + 2^n

T(n) = 2^n T(2) + 2(2^n -1);

The order will be O(n).

- pintuguptajuit August 01, 2012