Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

I'm working exercises on solving recurrences, just using subsitution, master theorem is after this chapter. I'm sort of stuck on one of the exercises. It states that:

The solution of $T(n) = 2T(\lfloor n/2 \rfloor) + n$ is $O(n \lg n)$. Show that it's also $\Omega(n \lg n)$ and conclude that the solution is $\Theta(n \lg n)$.

For showing that it's $O(n \lg n)$, I've to show that $T(n) \leq cn \lg n$. This can be solved by choosing an $m < n$, like $\lfloor n/2\rfloor$, and substituting.

But if we arrive at the conclusion that $T(n) \leq cn \lg n$ for any appropriate $c > 0$ and $n \geq n_0$, than how can we say that it is also $\Omega(n \lg n)$ which implies that $T(n) \geq cn \lg n$?

Some more clarification would be nice!

share|improve this question
    
The constants $c$ and the "sufficiently large n" $n_0$ can be different. –  mayank Jan 12 '13 at 10:59
    
By that, I mean these constants for showing the upper bound can be different from these constants for the lower bound. –  mayank Jan 12 '13 at 11:05
    
@mayank why don't you make this into an answer? –  Pål GD Jan 12 '13 at 12:20
    
Answers of this question may be helpful. –  Raphael Jan 12 '13 at 16:33
add comment

1 Answer 1

First, I would like to modify your statement slightly to remove any chance of confusion. When you say, "... $T(n) \le cn\log n$ for any appropriate $c > 0$ and $n \ge n_0$", it actually means $T(n) \le cn\log n$ for some appropriate $c > 0$ for all $n \ge n_0$.

Next, these constants for proving the lower bound can be (and generally are) different from these when proving the upper bound. I will demonstrate with your example:

Upper bound:
$T(n) = 2T(\frac{n}{2}) + n \le 2(c\cdot\frac{n}{2}\log{\frac{n}{2}}) + n$ (induction hypothesis)
$T(n) \le cn\log n - cn\log 2 + n = cn\log n - (c - 1)n$
$T(n) \le cn\log n$ for all $n$ for any $c \ge 1$
Therefore, $T(n) = O(n\log n)$

Lower bound:
I'll use a different constant $b$ for this, just to emphasize that the two constants are different.
$T(n) = 2T(\frac{n}{2}) + n \ge 2(b\cdot\frac{n}{2}\log{\frac{n}{2}}) + n$ (induction hypothesis)
$T(n) \ge bn\log n - bn\log 2 + n = bn\log n + (1 - b)n$
$T(n) \ge bn\log n$ for all $n$ for $0 \le b \le 1$
Therefore, $T(n) = \Omega(n\log n)$

So basically, you need to choose some constant such that the inequality holds for all sufficiently large $n$. These constants can (and generally are) different for different inequalities.

Note: I have assumed that $n$ is a perfect power of 2 in the above recursions to do away with the floor function. For asymptotic analysis, they do not really matter. These notes may help things become clearer.

share|improve this answer
add comment

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.