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

Improve this question
$\endgroup$
1
  • $\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
    Commented Dec 12, 2018 at 3:49

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
4
  • $\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
    Commented Sep 30, 2018 at 18:25
  • $\begingroup$ I just update my answer as well. $\endgroup$
    – John L.
    Commented Sep 30, 2018 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
    Commented Oct 1, 2018 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.
    Commented Oct 2, 2018 at 2:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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