Proving little o by first principles

Question

I'm trying to prove that $15n+7$ is $o(n\log n)$ (by first principles, i.e. no limits).

My idea is to solve for n to determine $n_0$ and then work backwards from there. But I can't seem to find a way.

$15n+7 < cn\log n$

$7 < n(c\log n-15)$

I got stuck here.

Answer 1

If $15n+7$ is $o(n \log n)$ then

$$15n+7 < cn \log_2n$$

for every $n \geq n_0$ for some positive real $c$ and $n_0$.

$$7 < n(c\log_2n - 15)$$

If we chose $n_0 = 1$ then this would change to $7 < -15$ which is false, so we need a larger $n$. Let's do $n_0 \geq 2$.

$$7 < 2(c - 15) = 2c - 30$$

And $7 < 2c -30$ is true for $c > 18.5$, so the proof is complete.

Answer 2

The problem is to prove that $$ \bigg( \frac{15n + 7}{n\log n} \bigg) \to 0 $$ as $n \to \infty$; for then we have by definition $15n + 7$ is $o(n\log n)$.

If $n > 1$, then $$ \frac{15n + 7}{n\log n} = \frac{15}{\log n} + \frac{7}{n\log n} < \frac{15}{\log n} + \frac{7}{(\log n)^{2}}. $$ Let $\varepsilon > 0$. Note that we have $$ \frac{15}{\log n} < \frac{\varepsilon}{2} $$ if $n > e^{30/\varepsilon} =: n_{1}$ and that we have $$ \frac{7}{(\log n)^{2}} < \frac{\varepsilon}{2} $$ if $n > e^{\sqrt{14/\varepsilon}} =: n_{2}$. So taking $n_{0} := \max \{ 1, n_{1}, n_{2} \}$ suffices.