0
$\begingroup$

I've already proven the statement using the limit definition of $o(g(n))$ and Stirling's approximation, but how do I prove it using the main definition for $o$ notation provided in CLRS instead?

Definition: $f(n) = o(g(n))$ if for all $c > 0$ there is $n_0 > 0$ such that $0 \leq f(n) < cg(n)$ for all $n > n_0$.

I've tried substituting Stirling's approximation again, but I am unaware of any analytic means of determining $n_0$ as a function of $c$ due to the presence of the $n$ term as both a base and exponent in the resulting inequality.

$\endgroup$
5
$\begingroup$

You do not need anything as fancy as Stirling. It is easy to see that $n!\cdot n < n^n$ for all $n>2$ (just compare the first two terms of $n!=1\cdot 2\cdot\ldots$ witht those of $n^n=n\cdot n\cdot\ldots$).

$\endgroup$
8
  • $\begingroup$ I missed completely that he asked the trivial question. Proving how n! is related to n^n e^-n, that would be a lot more tricky. $\endgroup$ – gnasher729 Sep 28 '20 at 10:12
  • $\begingroup$ Prove that n! = o (n^n 2^-n): Split the product into the numbers 1 to n/8, n/8 to 2n/8, 2n/8 to 3n/8 etc. $\endgroup$ – gnasher729 Sep 28 '20 at 10:22
  • $\begingroup$ I know it's easy to see that n! < n^n for all n > 2. My question wasn't what the general intuition behind the claim was. I was wondering how you would prove the claim formally using the definition I provided in my question. What would your choice of n_0 be for every choice of c? If c = 0.0001 for instance, then you can't say n! < cn^n simply "for all n>2". $\endgroup$ – kotu Sep 28 '20 at 15:39
  • 1
    $\begingroup$ @kotu I do not want to give a detailed exposition because I don't want to accidentally do someone's homework. If you let $n_0 > 1/c$ you just need to use elementary algebra on the expression $n!\cdot n <n^n$ to derive that $n!<cn^n$. $\endgroup$ – Tom van der Zanden Sep 29 '20 at 9:12
  • 1
    $\begingroup$ @kotu I just needed any kind of separation between the functions. That $n!\cdot n < n^n$ occured to me after comparing the expansion of $n!$ and $n^n$ and it was the simplest inequality you can easily prove from comparing the expansions. To see that $n>1/c$ observe that $n^n$ is bigger than $n!$ by (at least) a factor of $n$. So, if we have a very small $c$ in front of $n^n$ - making it smaller by a factor $1/c$, we need to make it bigger by $1/c$ again by assuming $n>1/c$. It is essentially just the same as proving $n=o(n^2)$. $\endgroup$ – Tom van der Zanden Sep 29 '20 at 20:44

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.