Welcome to our community

Be a part of something great, join today!

Big O problem

lemonthree

Member
Apr 11, 2016
51
Let \(\displaystyle \mid h \mid \)< 1. Which of the following functions are O(h)? Explain.
\(\displaystyle -4h \)
\(\displaystyle h+h^2 \)
\(\displaystyle \mid h \mid ^{0.5} \)
\(\displaystyle h + cos (h) \)

Based on my notes, f(h) = O(h) only if \(\displaystyle \mid f \mid \) ≤ C \(\displaystyle \mid h \mid \), where C is a constant independent of h.

I can only solve for the first function -4h, as I can take C = -4 to give \(\displaystyle \mid f \mid \) = -4 \(\displaystyle \mid h \mid \)
For the rest, I am not very sure how I should go about solving since I cannot get C to be a constant independent of h. Are there any tips to solving them? Although I am guessing that the remaining functions are not O(h) anyways...

I tried searching the net but the results led me to general cases of O(h), O(log(h)) type which does not go into detail the math part behind it.
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
9,265
The condition only has to hold for h taken to infinity.
 

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,525
I think the concept of $O(h)$ is defined not only for $h\to\infty$, but $h$ does have to tend somewhere, whether to a finite or infinite limit. In this problem the limit of $h$ is not given, which is a mistake. But since $|h|<1$, one may suggest that $h\to0$. Then indeed $\lvert-4h\rvert=4|h|$ (note that $\lvert-4h\rvert=-4|h|$ is incorrect), so $-4h=O(h)$ when $h\to0$.

Next $|h+h^2|\le|h|+|h^2|\le2|h|$ because $|h^2|<|h|<1$, so $h+h^2$ is also $O(h)$ when $h\to0$.

$|h|^{0.5}$ is not $O(h)$. If there were a $C$ such that $\sqrt{|h|}\le C|h|$ for all $h$ in some neighborhood of $0$, then $\sqrt{|h|}/|h|\le C$ in that neighborhood, but $\lim_{h\to0+}1/\sqrt{h}\to\infty$.

What do you think about $h+\cos h$?
 

lemonthree

Member
Apr 11, 2016
51
$\left | h + cos(h) \right | \leq C \left | h \right |$ And by taylor series, I know that $ h + cos(h) = h + (1-\frac{h^2}{2!}...) $

So solving for the equation, as h tends to 0, lhs tends to infinity while rhs is a constant. This is a contradiction, so h + cos h is not O(h)
 

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,525

lemonthree

Member
Apr 11, 2016
51
Which equation and what do you want to find from that equation?

What exactly tends to infinity?
$\left | h + cos(h) \right | \leq C \left | h \right | $can be written as
$\left |h + (1-\frac{h^2}{2!}...) \right | \leq C \left | h \right |$
$\frac{\left |h + (1-\frac{h^2}{2!}...) \right |}{ \left | h \right | } \leq C$

The $\frac{1}{\left | h \right |}$ part in the left hand side equation tends to infinity, while right hand side C is a constant...
So there is a contradiction here.
 

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,525
This is correct, though I would not use Taylor series and division. It is know that $\cos h\ge\sqrt{3}/2>4/5$ when $|h|<1/2<\pi/6$. Therefore $|h+\cos h|\ge 4/5-1/2=3/10$ when $|h|<1/2$. If there exist constants $C>0$ and and $\delta>0$ for which $|h+\cos h|\le C|h|$ for all $-\delta<h<\delta$, then $3/10\le|h+\cos h|\le C|h|$ for all $-\min(\delta,1/2)<h<\min(\delta,1/2)$, which is a contradiction.