Question

Solve recurrence by substitution method T(n)=2T (n-2) +2​

Answer 1

Answer:

Solution by Substitution Method

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

Substitute n/2 into the main equation

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

And T(n) = 4T (n/4) + 2n Again by substituting n/4, we can see

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

And T(n) = 8T(n/8) + 3n Continuing in this manner, we obtain

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

Using k = Ign T(n) = nT(1) + nlgn = nlgn + n

T(n) = O(nlgn)