retagged by
1,579 views

1 Answer

Best answer
2 votes
2 votes

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

T(n) = 24 T(n/22) + 4C + C

T(n) = 26 T(n/23) + 42C + 4C + C

T(n) = 28 T(n/24) + 43C+ 42C + 4C + C

and so on... (Now you will get a pattern)

Let n = 2k , Hence k = logn.

From the above pattern we can write

T(n) = 22k T(n/2k) + 4k-1C + 4k-2C + ..... + C

T(n) = 22k T(1) + (4k-1 + 4k-2 + .... + 1) C           (G.P of K terms with initial term is 1)

T(n) = 22logn + 1*(4k - 1)/3 * C

T(n) = n2 + (22k -1) /3

T(n) = n2 + (n2 -1)/3

T(n) = O(n2)

This is the exact solution by substitution  . :)

But these kind of questions should be directly solved using master's theorem.

edited by

Related questions

1 votes
1 votes
2 answers
1
5 votes
5 votes
1 answer
2
2 votes
2 votes
2 answers
3
NIHAR MUKHIYA asked Jul 2, 2017
3,340 views
solution of t(n)= t(sqrt(n)) + n using back substitution