2
$\begingroup$

I'm reading the book Introduction to Algorithms and in Chapter 3 it is said that if $f(n)$ and $g(n)$ are asymptotically positive then

$$ f(n) = O(g(n)) \text{ and } g(n) = O(h(n)) \text{ implies } f(n) = O(h(n)) $$

However, I don't see why this wouldn't also be valid if you just required $f(n)$ and $g(n)$ to be asymptotically nonnegative.

Edit: Here is the definition of $O$ used in the book:

$$ \begin{aligned} O(g(n)) = \{f(n):&\text{ there exist positive constants $c$ and $n_0$ such that}\\ &0 \le f(n) \le cg(n) \text{ for all } n \ge n_0 \} \end{aligned} $$

$\endgroup$
1
$\begingroup$

Suppose $f(n)$, $g(n)$ and $h(n)$ are asymptotically non-negative functions such that $f(n) = O(g(n))$ and $g(n) = O(h(n))$.

Then, by definition, there exist positive constants $c_1, c_2, m_1, m_2$ such that

$$ 0 \le f(n) \le c_1 g(n) $$

whenever $n \ge m_1$ and

$$ 0 \le g(n) \le c_2 h(n) $$

whenever $n \ge m_2$.

Choose $c = c_1 c_2$ and $n_0 = \max\{m_1, m_2\}$. Note that both $c$ and $n_0$ are positive. Then, whenever $n \ge n_0$, we have

$$ 0 \le f(n) \le c_1 g(n) \le c_1 c_2 h(n) = c h(n) $$

which implies that $f(n) = O(h(n))$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.