1
$\begingroup$

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.

Improve this question
$\endgroup$
2
0
$\begingroup$

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

Improve this answer
$\endgroup$
21
  • 1
    $\begingroup$ In mathematics we are allowed to use whatever tools we wish. We can use calculus if we wish. We can use linear algebra if we wish. We can use complex analysis if we wish. The only rule is that the argument should be logically valid. $\endgroup$ – Yuval Filmus Nov 1 '20 at 13:24
  • 1
    $\begingroup$ In this problem, we can use induction to prove that $n \geq \log n$ for large enough $n$, but I see no reason to tie my hands behind my back just because your textbook doesn't mention calculus. Calculus is part of the common toolkit of all mathematicians. $\endgroup$ – Yuval Filmus Nov 1 '20 at 13:26
  • 1
    $\begingroup$ This is a good reason to become friends with calculus, which is the basis of all modern science. As you can see, the inductive proof is much less clean. $\endgroup$ – Yuval Filmus Nov 1 '20 at 13:54
  • 1
    $\begingroup$ Even if you determine a point at which $2n_0^2 = 8n_0\log n_0$ (which you can find numerically), this doesn't automatically guarantee that $2n^2 \geq 8n\log n$ for all $n \geq n_0$. You have to prove it somehow. $\endgroup$ – Yuval Filmus Nov 1 '20 at 15:29
  • 1
    $\begingroup$ I'm afraid that's false for $n=2,\ldots,8$ (assuming that by $\log$ you mean natural logarithm). You can check it yourself. This shows that your heuristic fails. $\endgroup$ – Yuval Filmus Nov 1 '20 at 16:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.