Problem in substitution

Question

I have a very stupid question, it seems that I've forgotten most of my math and can't figure this out.

Considering the following,

For example consider the recurrence T(n) = 2T(n/2) + n

We guess the solution as T(n) = O(nLogn). Now we use induction
to prove our guess.

We need to prove that T(n) <= cnLogn. We can assume that it is true
for values smaller than n.

T(n) = 2T(n/2) + n
    <= cn/2Log(n/2) + n
    =  cnLogn - cnLog2 + n
    =  cnLogn - cn + n
    <= cnLogn

Now, I'm at a loss to how 2T(n/2) became cn/2Log(n/2). I'm guessing that n was replaces by cnLogn. But how does the rest of it follow?

Thanks.

Answer 1

We can take $c\ge 1$ without loss of generality.

Then \begin{eqnarray}T(n) &\le& 2 c {n \over 2} \log_2 {n \over 2} + n \\ &\le& cn (\log_2 {n \over 2} +1) \\ &=& cn ( \log_2 n -1 + 1) \\ &=& cn \log_2 n \end{eqnarray}

Answer 2

Without using induction

Notice the pattern

Since T(n) = 2T(n/2) + n then we have T(n/2) = 2T(n/4) + n/2
and so T(n)  = 2(2T(n/4) + n/2) + n  = 4T(n/4) + n + n  = 4T(n/4) + 2n
We know do the same thing over and over again like follows
     = 4(2T(n/8) + n/4) + 2n = 8T(n/8) + n + 2n = 8T(n/8) + 3n
     = 8(2T(n/16) + n/8)+ 3n = 8T(n/16)+ n + 3n = 16T(n/16) + 4n
     ...                                        = 32T(n/32) + 5n
     ... now we have n/32 as in the 
        form of n/2^k right now we want   n/2^k =1 so
         n = 2^k and so log n = k and so
                                                = nT(1) + log2(n)n
                                                = O(nlog2(n))