Substitution method

Question

I just wanted to verify some things did I do the steps below right?

T(n)   = 3T(n/3) + n  : Theta(nlogn)

O(nlogn)

T(k)   = cklog(k)  k<n

T(n/4) = c(n/3)log(n/3)
       = c(n/3)[logn - log3]
       = c(n/3)logn - c(n/3)log3    

T(n)   = cnlogn-cnlog3 + n

       <= cnlogn -cn + n 
       <= cnlogn -dn **[STEP A]**
       <= cnlogn if c >= d

Omega(nlogn)
   >= cnlogn -cn + n 
   >= cnlogn -dn **[STEP A]**
   >= cnlogn if 0 < c <= d  

I'm having trouble with step A what I ended up for my ranges of c was:

c >= 1 for the upper bound 0 < c <= 1 for the lower bound

Is there a special reason why you would combine cn + n. I can kind of see the logic behind it but is it necessary to do that step? Because then I can do that for like any case...which is a bit weird..

Answer 1

You were still right until:

T(n) = cnlogn-cnlog3 + n
     >= cnlogn -cn + n

for Ω(nlogn)

since it only holds for c <= 0 which is contradictory with our assumption that c >= 0.

One way to fix the second proof could be:

T(n) = cnlogn - cnlog3 + n
     = cnlogn - n(clog3 - 1)
     <= cnlogn when c >= 1/log3 

Therefore: T(n) = Ω(nlogn).

In general, values of lower bound and upper bound don't matter much. The goal is to find two constants c1 and c2 such that:

c1*n*logn <= T(n) <= c2*n*logn forall n >= some n0.