# Understanding O(h): Examining Functions with h as an Input

• MHB
• lemonthree
In summary, the functions -4h and h+h^2 are O(h) as they satisfy the condition of f(h) = O(h) when |f| ≤ C |h|. However, the function |h|^0.5 is not O(h) as it does not satisfy the condition. The function h+cos(h) is also not O(h) as it leads to a contradiction when trying to find a constant C that satisfies the condition.
lemonthree
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.

The condition only has to hold for h taken to infinity.

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$?

$\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)

lemonthree said:
So solving for the equation, as h tends to 0
Which equation and what do you want to find from that equation?

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

Evgeny.Makarov said:
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.

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.

## 1. What is O(h) in terms of functions?

O(h) is a notation used in computer science and mathematics to describe the time complexity of a function. It represents the upper bound on the growth rate of a function as its input, h, increases.

## 2. How is O(h) different from other notations like O(1) or O(n)?

O(h) specifically focuses on the growth rate of a function as its input increases, whereas O(1) represents constant time complexity and O(n) represents linear time complexity. O(h) is used when the time complexity of a function is dependent on a specific input, h, rather than the overall size of the input.

## 3. What are some common examples of functions with O(h) time complexity?

Functions with O(h) time complexity include searching algorithms like linear search, as well as some sorting algorithms like bubble sort. These functions have a time complexity that is directly proportional to the size of the input, h.

## 4. How can understanding O(h) help with optimizing code?

By understanding O(h), you can identify which parts of your code may be slowing down the overall performance. If a function has a time complexity of O(h), you can look for ways to reduce the growth rate of h in order to improve the efficiency of your code.

## 5. Is O(h) the only notation used for time complexity?

No, there are other notations used to describe time complexity, such as Ω(h) which represents the lower bound of a function's growth rate, and Θ(h) which represents the average case time complexity. It is important to consider all of these notations when analyzing the efficiency of a function.

Replies
2
Views
1K
Replies
3
Views
1K
Replies
5
Views
4K
Replies
36
Views
7K
Replies
8
Views
2K
Replies
1
Views
1K
Replies
53
Views
1K
Replies
6
Views
1K
Replies
3
Views
2K
Replies
5
Views
2K