Big-Oh proof with (n+1)!

Asked Oct 07 '20 at 20:43

Active Oct 07 '20 at 20:50

Viewed 58 times

Prove that $T(n) = (n+1)! + 2^n$ is $O((n+1)!)$.

Proof: by Big-Oh definition, $T(n)$ is $O((n+1)!)$ if $T(n) \leq c\cdot (n+1)!$ for some $n\geq n_0$.

Let us check this condition. If $(n+1)! + 2^n \leq c\cdot(n+1)!$ then (this is the part I am having trouble with. I cannot find a way to divide through the inequality to show the proof.) <= c. Therefore, the Big-Oh condition holds for $n\geq n_0 =$ ? and $c \geq$ ?.

The question is how can I arrange the expression to be able to prove that this is $O((n+1)!)$?

edited Oct 07 '20 at 20:50

Alann Rosas

5,421
1
9
28

asked Oct 07 '20 at 20:43

erwoods89

1

$2^n \leq (n+1)!$ for $n \geq 0$ – Sil Oct 07 '20 at 20:51
@Sil Would you mind giving a bit of clarification? – erwoods89 Oct 07 '20 at 20:59
1

As to why it holds? You can prove that by induction, it's also clear from $2\cdot 2 \cdots 2 \leq 2 \cdot 3 \cdots (n+1)$ where there are $n$ terms on both sides. – Sil Oct 07 '20 at 21:01
@Sil Thank you, I used PMI. Looks good! – erwoods89 Oct 07 '20 at 21:18
You are welcome! – Sil Oct 07 '20 at 21:19

Big-Oh proof with (n+1)!

0 Answers0