Interview Question
0of 0 votesSolve T(n) = 2T(n/2) + 2.
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