0

To solve this question , I came up below kinda solution: $ d^n $ $\leq n!$

$\frac{d^n}{n!} \leq$ constant

But how am I prove this. By the way this is Big Oh Notation

usukidoll
  • 2,074
hacikho
  • 53
  • 7
  • It suffice to show that $\lim_{n\to \infty} \frac{d^n}{n!}\le C$ for some constant $C$, in fact you may take $C=0$. – Ma Ming Feb 10 '14 at 01:09
  • 1
    It's not quite true to say that $d^n/n!$ has to be less than or equal to a constant -- it only has to be eventually true. (That is: if you pick a $c$, what you actually need is that $d^n/n! \leq c$ for every $n>N$ where you get to choose the $N$. Hence it only has to be true in the limit, as Ma Ming says above.) – tabstop Feb 10 '14 at 01:12

1 Answers1

0

You need to use proof by induction, choosing a suitable constant. $d^n$ is $O(n!)$ if there is a constant $c$ such that $d^n \le cn!$ for large enough $n$.

Choose the constant $c = d^d$.

Base case. For all $n\le d$, $d^n \le c n!$ because $c=d^d$ and $d^n\le d^d, \forall n\le d$

Induction case. Assume for some $k>d$, $d^k \le ck!$. Multiply both sides by $d$ to get $d^{k+1} \le cdk!$, but $d<k<k+1$, so $cdk! \le c(k+1)k! = ck!$. Hence $d^{k+1} \le (k+1)!$.

TooTone
  • 6,343