2,441 views
1 votes
1 votes
Given RR as -

T(n) = 2T(n/2)+n ; n>1

T(1) = 1

Solve this using only BACK SUBSTITUTION method?

 

Note - I am stuck at T(n)= 2^k.T(n/2^k)+(2^k-1).n

and I'm putting 2^k=n

 

Please help me I am getting wrong answer!

1 Answer

2 votes
2 votes

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

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

Put (2) in (1)

$\therefore$ T(n) = 2 { 2T(n/4) + n/2  } + n

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

      =  23T(n/8) + n + n + n

      = 24T(n/16) + n + n + n + n

      = 2kT(n/2k) + n + n + n + n + n.....(k times n will be present)

      = 2kT(n/2k) + nk

Now put 2k = n, so k will be log2n

So, T(n) = nT(2k/2k) + nlog2n

            = nT(1) + nlog2n

            = n + nlog2n

Hence, T(n) = O( nlog2n )

Related questions

2 votes
2 votes
1 answer
1
indrajeet asked Feb 10, 2016
520 views
T(n) = 2*T(n/2) + n*logn please explain
3 votes
3 votes
1 answer
2
sampad asked Nov 23, 2015
521 views
Solve the equation: $$a_n = 5a_{n/3} + 7, \;\; a_1 = 5$$Note: $a_0$ is not given.
0 votes
0 votes
0 answers
3