Proving that $3n^2 + n \log_2n - 2$ is $\Theta (n^2 - 5n +1)$

Question

Specifically the following: $3n^2 + n \log_2n - 2 \in \Theta (n^2 - 5n +1)$

I'm aware it needs to be $g(n)c_1 \le f(n) \le g(n)c_2$, where $g(n)$ is $\Theta (n^2 - 5n +1)$ and $f(n)$ is $3n^2 + n \log_2n - 2$, but I have no idea how to go about solving this.

My professor was less than helpful when explaining, so if you could explain in general terms that I can apply to other similar problems, I would appreciate it.

Thanks.

Answer 1

How we do it...

We need to show $$c_1\ g(n) \leq f(n) \leq c_2\ g(n)$$ holds for sufficiently large $n$.

Let's do the upper bound (the approach for the lower bound is similar). We want to find a constant $c_2>0$ such that $$3n^2+n \log_2 n -2 \leq c_2\ (n^2-5n+1)$$ for sufficiently large $n$. We see that the leading term on the left-hand side is $3n^2$ and the leading term on the right-hand side is $c_2 n^2$, so let's try $c_2=5$ (just a guess, but we'd want $c_2$ to be greater than $3$, otherwise it definitely won't work).

So, we want to show $$3n^2+n \log_2 n -2 \leq 5n^2-25n+5$$ for sufficiently large $n$. This happens if and only if $$n \log_2 n \leq 2n^2-25n+7 \qquad (*).$$ For $n \geq 1$, the bound $(*)$ holds if $$n^2 \leq 2n^2-25n+7$$ holds (since $n \geq \log_2 n$), or equivalently if $$n^2-25n+7 \geq 0 \qquad (**).$$ The bound $(**)$ holds when $n \geq 25$.

[It's a matter of personal preference whether or not this needs to be proved, but just in case: if $n=25+a$ for some $a \geq 0$, then $$n^2-25n+7=(25+a)^2-25(25+a)+7=25^2+50a+a^2-25^2-25a+7=25a+7 \geq 0.]$$

How we present it...

So, going backwards, we found the chain of implications: \begin{align*} n \geq 25 & \implies n^2-25n+7 \geq 0 \\ & \implies n^2 \leq 2n^2-25n+7 \\ & \implies n \log_2 n \leq 2n^2-25n+7 \\ & \implies 3n^2+n \log_2 n -2 \leq 5n^2-25n+5 \\ & \implies 3n^2+n \log_2 n -2 \leq c_2\ (n^2-5n+1). \end{align*} And this is the proof (and such proofs are often presented in a way that omits the roundabout way of deriving them).

Comments...

Coming up with this is tricky:

1. We're accustomed to reading and writing proofs in the "forward direction":

   We prove $A$ is true, and $A \implies B$, $B \implies C$, and $C \implies D$. We conclude that $D$ is true.

   Instead here, we know what we want to prove $D$, and we work "backwards":

   We prove $D \impliedby C$, $C \impliedby B$, and $B \impliedby A$ where $A$ is "$n \geq k$" for some $k$.

2. Along the way, we have to make guesses that might not pan out. E.g., before I tried $c_2=5$, I tried $c_2=4$, and later realized that $c_2=5$ was easier to work with (and started over again).