2
$\begingroup$

how I can logically understand this is false ($c$ is constant):

$ \frac{n!}{c} \leq 2^n$

why it was false for large value from asymptotic notation concept? ( i see this is true for some $n < n_0$ but not hold for large value).

$\endgroup$
2
  • $\begingroup$ This inequality is false for large $n$. The "asympotic notation concept" can't tell you that. You have to prove it directly (you say you can "see this.) Then you make the asymptotic statement. Just how large $n$ has to be depends on $c$. $\endgroup$ Dec 12, 2020 at 19:26
  • $\begingroup$ @BettyAnderson See my answer. $\endgroup$ Dec 12, 2020 at 19:47

1 Answer 1

2
$\begingroup$

For each value of $c$ you can find out exactly where the inequality switches over by checking numerically. For example, for $c=3$ the change is between $n=4$ and $n=5$. There is no formula.

The argument that for any particular $c$ it happens eventually does not depend on knowing just where. It usually does not matter just where - that's when knowing what happens "asymptotically" is all you care about.

Edit in response to comment.

You have to show that for any particular $c$, eventually $$ x_n = \frac{n!}{2^n} > c. $$ When $n > 5$, show that each $x_n$ is more than twice its predecessor. That should be enough to finish the proof.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .