Using the definition of $f$ is $O(g)$ proof:

Question

I'm studying for my discrete math class and I don't understand how to prove big O notation. I understand that $f$ is $O(g)$ of another if $f(x) \le c g(x)$ holds.

1. How would I go about proving $\sin x$ is $O(1)$ using the definition.

2. Also how do you disprove? Suppose you're asked to disprove that $\frac {x^3+x} {x+1}$ is not $O(x)$ using the definition?

Can you show me the steps and explain why each step was applied in simple terms?

EDIT: How would you do a question like this $e^x$ is not $O(x^5)$ Big O or/and $1$ is not $O(1/x)$.

Answer 1

For a), simply take $c=1$. Anyway, any constant larger than $1$ is okay.

For b), suppose by contradiction that there exists $C>0$ such that $$\frac{x^3+x}{x+1} \le C x$$ Multiplying by $1/x$ gets you $$\frac{x^2+1}{x+1} \le C $$ But this implies that $\frac{x^2+1}{x+1}$ is bounded, contradicting $$\lim_{x \to \infty} \frac{x^2+1}{x+1} = + \infty$$

Answer 2

Notice that, in general, $\sin x \le 1 = 1 \cdot 1$, so it is trivial to understand that $\sin x$ is $O(1)$ where $c=1$.

For the second, assume that there exist $c>0$ such that $\frac {x^3 + x} {x+1} \le cx$; usually these problems are given for $x>0$, so your assumption would be equivalent to $x^3+x \le cx^2 + c$, or $x^3 - cx^2 + x - c \le 0$, but this is clearly false because that 3rd degree polynomial tends to $\infty$ (which is positive) for $x \to \infty$. Hence, the assumption is false.