The definition of Big-O is $$u_n = O(v_n) \iff (\exists c \in \mathbb{R}^{*})\,\, (\exists N \in \mathbb{N}) \,\, n > N \implies u_n < c \, v_n$$

Based on that I am trying to find the upper bound for this function $log(n!)/log(n)^3$.

What I've done so far is:

$log(n!) = log(1) + log(2) + ... + log(n!) <= n*log(n) \implies log(n!) = O(n*logn) $

So, $log(n!)/log(n)^3 = O(n*log(n)/log(n)^3)$.

Can we simplify this even more by saying that: $O(n*log(n)/log(n)^3) = O(n)$ ?

  • $\begingroup$ Use $\log(x)$ for $\log(x)$. $\endgroup$ – Shaun Apr 2 at 13:28
  • 1
    $\begingroup$ How would you simplify $\log(n)/\log(n)^3$ ? $\endgroup$ – J. W. Tanner Apr 2 at 13:31
  • 1
    $\begingroup$ You are writing $O(f(n))=O(g(n))$, but I think you mean to write $f(n)=O(g(n))$. You can ignore the $\ln(n)^3$ in the denominator, but there is really no reason to do so. There's no "right" answer when it comes to big-$O$ notation. I could say $\ln(n!)=O(n^{1000})$ but that's not very useful. Big-$O$ notation is about simplifying expressions enough that we can understand how they grow, without throwing too much away. $\endgroup$ – kccu Apr 2 at 13:35
  • $\begingroup$ @J.W.Tanner oh lol my bad! Thanks $\endgroup$ – Dimitris Prasakis Apr 2 at 13:41
  • $\begingroup$ @kccu useful insights, thank you very much. $\endgroup$ – Dimitris Prasakis Apr 2 at 13:41

Your Answer

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

Browse other questions tagged or ask your own question.