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.
$\endgroup$ 13 Answers
$\begingroup$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}.$
$\endgroup$ $\begingroup$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
$\endgroup$ 2 $\begingroup$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.
$\endgroup$
