Proving that: $800 + n \log n + 600\sqrt n\log n = \Theta(n\log n)$

Question

I am trying to prove that

$$800 + n \log n + 600\sqrt n\log n = \Theta(n\log n)$$

(where $\log$ is base $2$)

Basically so far, I've reduced this expression into an inequality:

$$0 \le c_1 \le \frac{800}{n\log n} + 1 + \frac{600} {\sqrt n} \le c_2$$

From what I've been told, we only need to find ANY set of constants where this holds (where n goes to infinity).

ANY set of constants? Okay in that case: $n_0=5, c_2=400$ and $c_1=1$ works.

But, have I completed the proof or am I missing something? Are my constants valid or do they have to be more specific?

Thanks in advance.

Answer 1

The set $n_0=5$, $c_2=400$ and $c_1=1$, and the steps leading to it in the question, are perfect.

After a while, in many situations, one can even omit computing some explicit $(n_0,c_1,c_2)$, for example every time the ratio actually converges. For example, in your case, to note that $$\frac{800}{n\log n} + 1 + \frac{600}{\sqrt{n}}$$ converges to some positive limit (here, the limit is $1$) is enough to ensure the $\Theta(n\log n)$ property.

Answer 2

That appears (at a glance...) to be correct. But to complete the proof (at least in a first course!) you need to show that for all $n > n0$, your function's values lie between $c_1$ and $c_2$. That involves writing a proof. For this one, a little calculus would probably do the trick, but so would many other approaches.

IF you were writing a paper for a journal of computer science, you could probably just write down $n_0, c_1$, and $c_2$ and folks would look and think "yeah, that looks right." More likely, you'd just say "and because THIS is O(THAT), ..." and everyone would nod. But to get to that point, you have to prove you know what you're doing. :(

The remainder of your proof might look like this:

Pick $n_0 = 5$, $c_1 = 1$, $c_2 = 401$. (You'll see why I picked 401 a little lower down).

Then observe that for $n > n_0 = 5$, we have $n \log n > 1$, so $\frac{1}{n \log n} < 1$. Further, for $n > n_0$, $\sqrt{n} > 2$, so $\frac{1}{\sqrt{n}} < 2$. And finally, it's evident that $800 < 100 n \log n$, since $n > 5$, and $\log n > 1.6$.

Thus \begin{align} 0 &\le 800 + n \log n + 600\sqrt{n} \log(n) \\ &\le 800 + n \log n + 600 \frac{n}{\sqrt{n}} \log n\\ &\le 800 + n \log n + 600 \frac{n}{2} \log n\\ &\le 800 + n \log n + 300 n \log n\\ &\le 800 + 301 n \log n\\ &\le 100 n \log n + 301 n \log n\\ &\le 401 n \log n\\ \end{align}

Your version of this proof would have put more things in the denominator -- it might be worth writing it out! -- but I find that it's easy, when including a division, to lose the sign-change in an inequality, so I prefer to avoid divisions when possible. It's a matter of taste, I suppose (and experience with screwing things up!).