Please explain how you attacked these questions step by step. 1) 1 is not O(1/x). 2) e^x is not O(x^5)

Question

I'm studying for my discrete math class and I don't fully understand how to proof how a function is not a big O for certain questions. I understand that you have to assume that it is big O and proof by contradiction.
Please explain how you attacked these questions step by step.
1) 1 is not

O (\frac{1}{x})

2)

e^{x}

is not

O (x^{5})

Answer 1

Step 1
1) Suppose

1 = O (1 / x)

. Then there exists a constant C such that for all large x, we have

1 \leq C / x

. However, for all

x > C

we have

C / x < 1

, a contradiction.
Step 2
2) Suppose

e^{x} = O (x^{5})

. Then there exists a constant C such that for all large x we have

e^{x} \leq C x^{5}

. However,

\frac{e^{x}}{x^{5}} \to \infty

as

x \to \infty

, a contradiction. [As Peter suggests, use L'Hopital's rule multiple times, or expand the Taylor series for

e^{x}

.]

Please explain how you attacked these questions step by step. 1) 1 is not O(1/x). 2) e^x is not O(x^5)

Want to know more about Discrete math?

Answers (1)

Not exactly what you’re looking for?

You might be interested in

New questions