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..
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
.