Finding n0, asymptotic analysis

Question

I am attempting a textbook question about asymptotic analysis. The question goes:

** The number of operations executed by algorithms A and B is 8nlogn and 2n^2, respectively. Determine n0 such that A is better than B for n ≥ n0. **

So far my approach has been to draw a log-log graph with both lines and find the meeting point, I am thinking that this meeting point is at log(n0) so I can find n0 from it, the one that they are looking for, but things get strange here because the two lines never meet!

Here is the picture of my graph. https://drive.google.com/file/d/1eUFkawKXCWiRBV6BV34Acs5SK4mBHMN4/view?usp=sharing

Any help with this problem will be much appreciated.

Answer 1

In principle it could be that $2n^2 = 8n\log n$ could have several solutions. However, this doesn't matter much: the derivative of $n/\log n$ is $$ \frac{\log n - 1}{\log^2 n}, $$ and so if $2N^2 \geq 8N\log N$ for some $N \geq e$, it follows that $2n^2 \geq 8n\log n$ for all $n \geq N$.

Plugging in small values of $N$, we see that $2N^2 > 8N\log N$ for $N = 9$.

---

Here is an alternative proof. We first prove that if $n = e^k$ and $k \geq 4$ is an integer, then $2n^2 \geq 8en(\log n + 1)$. You can calculate that it holds for the base case $k = 4$. Assuming that it holds for some $k \geq 4$, we prove it for $k + 1$. The induction hypothesis implies that $$ 2e^{2(k+1)} = e^2 \cdot 2e^{2k} \geq e^2 \cdot 8ee^k (k+1) = 8ee^{k+1} (k+2) \cdot e \cdot \frac{k+1}{k+2}. $$ To complete the proof, it suffices to check that $e (k+1)/(k+2) \geq 1$, or equivalently, that $e \geq (k+2)/(k+1) = 1 + 1/(k+1)$, which trivially holds since $k \geq 4$.

Now let $n \geq e^4$ be arbitrary, and let $k = \lfloor \log n \rfloor$. Then $$ 2n^2 \geq 2(e^k)^2 \geq 2ee^k(k+1) > 2n\log n. $$