# Big O Notation Simplification in the fraction form

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], 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}$$

• 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)$. – Alex Smart Dec 12 '18 at 3:49

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.

• 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. – Maxfield Sep 30 '18 at 18:25
• I just update my answer as well. – John L. Sep 30 '18 at 23:56
• 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. – Maxfield Oct 1 '18 at 2:49
• 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$. – John L. Oct 2 '18 at 2:07