How do I show a function is Big-O of another function using the definition of Big-O?

Question

Definition: A function F(x) is Big-O of g(x) if we can find constant witnesses such that $f(x) <= Cg(x)$ when $x=k$.

Use the definition of “$f (x)$ is $O(g(x))$” to show that:

$x^4 + 9x^3 + 4x + 7$ is $O(x^4)$

I tried dividing both sides by $x^4$, but I'm not sure how to find a tight bound without repeatedly guessing and checking.

Another way to phrase this problem: After modifying C, so that $g(x)$ approximates $f(x)$, how would one find the intersection of the two functions.

P.S. I'm studying for a test so I'm looking for how to solve these problems in general.

Answer 1

The definition is that exists some constant $C>0$ such that $$\left|f\left(x\right)\right|\leq Cg\left(x\right)$$ as $x\rightarrow x_{0}$ , where $x_{0}$ can be $\infty.$ So I think you're interessed when $x\rightarrow\infty.$ In this case it's sufficient to note that $x^{4}$ grow up faster then other power of $x$, so $$x^{4}+9x^{3}+4x+7\leq x^{4}\left(1+9+4+7\right)=21x^{4}.$$ Note that if $x_{0}=0$, for example, this argument doesn't work, so be careful about $x_{0}.$

Answer 2

The definition of big-O says that $f=O(g)$ in the neighborhood of $x_0$ if and only if $\frac{f}{g}$ is bounded in that neighborhood. So at infinity one has $$\frac{x^4+9x^3+4x+7}{x^4}=1+\frac{9}{x}+\frac{4}{x^2}+\frac{7}{x^4}$$ By taking $x$ sufficiently large one can make $\frac{f(x)}{g(x)}\leq 2$ and we are done

Answer 3

Let $\textbf{f}$ and $\textbf{g}$ be two functions defined on some subset of the $\textbf{real numbers}$. One writes :

$f(x)=O(g(x))\text{ as }x\to\infty$

$\textbf{if and only if}$ there is a positive constant $\textbf{M}$ such that for all sufficiently large values of $\textbf{x}$ , the absolute value of $\textbf{f(x)}$ is at most $\textbf{M}$ multiplied by the absolute value of $\textbf{g(x)}$. That is $\textbf{f(x)} = \textbf{O(g(x))}$ if and only if there exists a positive real number $\textbf{M}$ and a real number $\textbf{x}$ such that

$|f(x)| \le \; M |g(x)|\text{ for all }x \ge x_0$

When $x = k, M = 1 + \frac{9}{k} +\frac{4}{k^3} + \frac{7}{k^4}$ . satisfies, so your approach was correct.