I've encountered these before, but never phrased or defined as follows, I'd like to know if I've done whatever the question wants to draw attention to (if it didn't want to draw attention to something, why would it be so far from the conventional big-oh questions?). I want to do it the most compact way, but the way the question wants! I feel I have missed the point of what the question wants, I have shown my method to prove to you lot I can do it, hence the long post, except for the last question at the bottom
"For each of the following pairs of functions $f,g:\mathbb{R}\rightarrow\mathbb{R}$ show that $f=O(g)$ as $x\rightarrow\infty$, giving an explicit $M>0$ and $x_0$ for which $|f(x)|\le M|g(x)|$ for $x>x_o$"
I've been spooked by the $\mathbb{R}$ domain, "well if it works for all $x>x_0$ I could just choose a positive $x_0$ then it's no different to what I can do already" - so why is it there. I also don't like the "as $x\rightarrow\infty$" but I can live with it.
Anyway:
a) $f=5x^2-2x+7$ and $g=x^5$
I want to show $|5x^2-2x+7|\le M|x^5|$ where $x>x_0$
I have a few options:
notice the discriminant of the quadratic is imaginary, and the coefficient of $x^2$ is positive, that means that quadratic is always greater than 0. $x^5$ is odd, this means it comes in from the bottom left and goes up to the bottom right, it also (at some point) gets larger than the quadratic. So they must intersect somewhere, That intersection is the lowest value of $x_0$ that can work. Doing this (graphic calculator FTW) yields $x_0=1.82$ and obviously $M=1$
Let $x>x_0\ge 0$ (which is fine right?) then $|5x^2-2x+7|\le M|x^5|\implies 5x^{-3}-2x^{-4}+7{x}^{-5}\le M$ now some thought, for $x>1$ $x^{-3}>x^{-4}$ so for $x>1$ this is getting ever smaller than what it was at $x=1$, so if we take $x_0=1$ then we get $M=10$
Both of these feel like I missed the point, they don't contain the spirit of big-oh, they don't really involve upper bounds at all. When dealing with the natural numbers as the domain this can be treated rather like a sequence, you want to show: $\forall n>n_0 \exists c>0, c\in\mathbb{R} : cg(n)-f(n)\ge 0$, that captures that upper bound concept, without asking for the best one, but also without any absolute values.
Questions
- $f=5x^2-2x+7$ and $g=x^2$ notice the different g
A few seconds of thought to think $f`=10x$(don't care about the rest) so if I choose an M such that g grows faster at some point (which will happen eventually if $2M>10$) g will catch up (as g(0)=0 < f(0)=7) eventually and they will intersect (twice), it's just a simple case of finding that point. again, seems to not contain the spirit of big-oh
- $f=5/x$ and $g=1$
This is trivial, without any thought $x_0=1$ and $M=5$ comes to mind. Imagining the graph you would sketch is all you need. again, this feels like graph work, not complexity
- $f=3x^2log(x)+5xlog^2(x)$ and $g=x^2log(x)$
again, graph work with some inequalities, $x>\log(x)$ now for $x\in(0,1)$ log will be negative, and with the log squared in there... lets sidestep this by defining $x>x_0=1$, now we have $3x^2log(x)+5xlog^2(x)<8x^2log(x)$ (the $x>1$ is important here as some interesting things happen when x=1, because log is zero, so for x=0 the above is an equality), the answer is now of the form $Mg$ so ... graph work done!
Lastly - and this is the same as the second one!!
- $f=\sum^k_{i=0}(a_ix^i)$ and $g=x^k$
Choose $kM>ka_k\implies M>a_k$ and eventually $Mx^k$ will overtake (if $|a_0|>0$ certainly). I'm not quite sure where to go algebraically from there.