Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have the following exercise:

We know that the solution of $T(n) = 2T(n/2) + n$ is $\mathcal{O}(n \log_2 n)$. Show that the solution of this recurrence is also $\mathcal{\Omega}(n \log_2 n)$. Conclude that the solution is $\mathcal{\Theta}(n \log_2 n)$.

To solve this i used the substitution method with induction and got the following solution:

$T(n) \ge 2\left(\dfrac{cn}{2}\right) \log_2 \left(\dfrac{n}{2}\right) + n$
$= cn \log_2\left(\dfrac{n}{2}\right) + n$
$= cn \log_2 n - cn \log_2 2 + n$
$= cn \log_2 n - cn + n$
which is larger than or equal to $cn \log_2 n$

for $c = 1$, we get equality.

If the same solution is valid for both the upper and lower bounds, that means that is valid for $\mathcal{\Theta}$, correct?

If my solution is wrong, please do elaborate.

Thank you for taking the time to help.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

You're okay until you say in the eighth line

which is larger than or equal to $cn\log_2n$

To be precise, you should note that $$ cn\log_2n-cn+n\ge cn\log_2n $$ if and only if $-cn+n\ge 0$, which is satisfied iff $c\le 1$. You correctly note that you do indeed have equality if $c=1$, but there are other values of $c$ which also satisfy the above inequality. Two lines later you're right to say that if the same solution (namely $c=1$) holds for upper and lower bounds then $T(n)=\Theta(n\log_2 n)$, but there's nothing that requires the $c$ values for the upper bound and the lower bound be the same.

One other point: your induction proof is missing a base case. If $T(1) =0$ then you'll indeed have $T(n)\ge n\log_2 n$ for all $n\ge 1$. Otherwise, you'll have $T(n)=nT(1)+n\log_2 n$. This is still $\Theta(n\log_2n)$, but I'd have docked you a point or two for not taking care of the base case.

share|improve this answer
    
thank you very much! I am still very new to this problematic but I'm finally starting to get the hang of it. Thanks for your complete answer! –  Peter Jan 18 '13 at 12:21

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.