Proving that $3n^2 + n \log_2n - 2$ is $\Theta (n^2 - 5n +1)$ 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.
 A: 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:


*

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


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