# Big O problem

#### lemonthree

##### Member
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
The condition only has to hold for h taken to infinity.

#### Evgeny.Makarov

##### Well-known member
MHB Math Scholar
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
$\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
So solving for the equation, as h tends to 0
Which equation and what do you want to find from that equation?

lhs tends to infinity while rhs is a constant.
What exactly tends to infinity?

#### lemonthree

##### Member
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
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.