I have a question on my homework which is:
Prove that if $f(x)=O(g(x))$, and $g(x)=O(h(x))$, then $f(x) = O(h(x))$
I am not to sure how to prove this. This is my attempt. Is it good enough or am i missing something important?
Thanks in advance!
if you Assume $f(x) = n^2+1$
then $f(x) \leq C_{1}.g(x)$ where $g(x) = x^2$
if $g(x)=x^2$
then $g(x) \leq C_{2}.h(x)$ where $h(x)=n^2$
Therefore this shows that $f(x) \leq C_3h(x)$ which proves $f(x) = O(h(x))$
$$f(x)=\mathcal O(g(x))\iff |f(x)|\le M|g(x)|\;,\;\;M\;\text{a constant}$$
$$g(x)=\mathcal O(h(x))\iff |g(x)|\le N|h(x)|\;,\;\;N\;\text{a constant}$$
thus
$$|f(x)|\le M|g(x)|\le MN(h(x))\ldots$$
Assuming the use of big o notation refers to the limiting behavior of $x$, as $x$ tends to $\infty$, then the following argument will work, if you are describing some other limiting behavior the requirements on x can be adjusted accordingly.
If we have for some $n_0$, that there exists a positive constant $M$, such that for all $x>n_0$ $$|f(x)|\leq M|g(x)|$$ And we also have for some other $a_0$, that there exists a positive constant $C$ such that for all $x>a_0$, $$|g(x)|\leq C|h(x)|$$ Then we may pick the maxima of either $n_0$ or $a_0$ so that we can say both statements hold for all $x>\text{max}{(a_0,n_0)}$, thus both inequalitys holds for the same range of x, and we are permitted to manipulate one with the other. From here we can deduce that $$|f(x)|\leq MC|h(x)|$$ For all $x$ such that, $x>\text{max}{(a_0,n_0)}$, which is the exact definition of $$f(x)=O(h(x))$$ Where the constant for which the absolute value of $f(x)$ is less then it times $h(x)$ is equal to $MC$, and the statement holds for all $x>\text{max}{(a_0,n_0)}$
A big warning for all proofs you do: Don't assume anything not given in the problem statement. For example, you don't know that the functions are quadratic. So that's a flaw in the proof.
Otherwise, you have the right idea. Just separate it from defining the function to be quadratic. Also, the last line should be an inequality, not an equality. That is, it should read $f(x) \le C_3 h(x)$, not $f(x) = C_3 h(x)$. (This is because $\mathcal{O}$ represents an upper bound, not an exact bound.)
