0
$\begingroup$

How should I approach this one a(n) = $\frac{n^3}{log^{3}(n)}$. As We can tell that $n^3$ grow much faster than $log^{3}(3)$. All of sudden, not sure what to do, found this [post][1], which is also in the fraction form, Do we calculate out $\frac{n^3}{log^{3}(n)}$ or just pick $n^3$. Eventually, the accurate number is not needed, but I somehow understand what it can simplify to and compare with other Big O, such as \begin{equation} 2^{n^{0.008}} \end{equation} Any hint is appreciated

Sorry for my first typo while using LaTex it is \begin{equation} 2^{n^{0.008}} \end{equation} instead of $(2^{n})^{0.0008}$

$\endgroup$
  • $\begingroup$ One simple way to check if $O(f(n))$ is the same as $O(g(n))$ is to take the limit $f(n)/g(n)$ as n approaches infinity. If the limit is zero or infinity, you know that the two are not equivalent. For instance $a(n)/n^3 \rightarrow 0$, so you know that $O(\frac{n^3}{log^3(n)})$ is strictly smaller than $O(n^3)$. $\endgroup$ – Alex Smart Dec 12 '18 at 3:49
2
$\begingroup$

It is indeed confusing if you are expecting some kind of simpler form.

However, ${n^3}/{\log^{3}n}$ is already in the simplest form in term of big-$\Theta$ notation. Consequently, it is also sort of the best form in term of big-$\Omega$ notation or big-$O$ notation. It is certainly true that $n^3/\log^3n = O(n^3)$. However, that kind of big-$O$ bound are usually frowned upon since it is obviously not tight, $n^3/\log^3n = o(n^3)$. In fact, in a similar vein, many time-complexities is described by $\Theta(n\log n)$, $O(n\log n)$ or $\Omega(n\log n)$, where the factor $\log n$ cannot be or is not removed.

The point is that although you can ignore the asymptotically insignificant terms in a sum to arrive at a simpler big-$O$ (or big-$\Theta$, big-$\Omega$) bound, you cannot do away with any unbounded factors without losing significant asymptotical information. For example, it is correct that $n^3+\log^{3}n=O(n^3)$ or $n^3+\log^{3}n=\Omega(n^3)$ or $n^3+\log^{3}n=\Theta(n^3)$, but neither $n^3/\log^{3}n=\Omega(n^3)$ nor $n^3\log^{3}n=O(n^3)$ is correct.

If you want to compare $n^3/\log^3n$ with $(2^{n})^{0.008}$, you can proceed as the following. $$\text{Since } n^3/\log^3n = O(n^3) \text { and } n^3=o((2^{0.008})^n), \text{ so } n^3/\log^3n =o((2^{0.008})^n)$$ where the second equality comes from the fact $2^{0.008}>1$ and the fact that any polynomial function grows slower than any increasing exponential function, which is proven in another answer of mine. Please note that I am using the little $o$-notation, which means basically "asymptotically growing slower than".

If you want to compare $n^3/\log^3n$ with $2^{n^{0.008}}$, you can proceed as the following. $$\text{Since } n^3/\log^3n = O(n^3) \text { and } n^3=2^{3\log_2n} = o\left(2^{(n^{0.008})}\right), \text{ so } n^3/\log^3n =o\left(2^{n^{0.008}}\right)$$ where the second equality comes from the fact $\log_2n=o(n^{0.008})$, which is also proven in that answer of mine since $\log_2n=(\log_2e)\log n$.

You can check the reference question and answers on sorting functions for good advices and more detailed and systematic treatment.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I am bit lost when you claim that $n^3$ =o($(2^{0.008})^n)$. can you please elaborate a little? Yes I have also update(correct) the \begin{equation} 2^{n^{0.008}} \end{equation}. to match exactly same as the book I am reading. $\endgroup$ – Maxfield Sep 30 '18 at 18:25
  • $\begingroup$ I just update my answer as well. $\endgroup$ – John L. Sep 30 '18 at 23:56
  • $\begingroup$ interesting. We actually need to compare which one is bigger \begin{equation} 2^{n^{0.008}} \end{equation} or $n^3/\log^3(n)$. but any both case, you all claim they are equal. $\endgroup$ – Maxfield Oct 1 '18 at 2:49
  • $\begingroup$ Apparently you did not see my usage of the small $o$-notation. That is NOT the big-$O$ notation as you understood. For example, $n^3/\log^3n =o((2^{0.008})^n)$ means $n^3/\log^3n$ grows slower than $(2^{0.008})^n$. $\endgroup$ – John L. Oct 2 '18 at 2:07

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.