Transitivity of asymptotic bounds
Suppose \( f(n) = \BigO{g(n)} \). This means, there exist some positive constant \( c \) such that for some values of \( n \ge n_0 \),
$$ 0 \le f(n) \le c g(n) $$
Now suppose there is another function \( h(n) \) that upper bounds \( g(n) \). This means, \( g(n) = \BigO{h(n)} \). By definition, it implies that there is some positive constant \( d \), such that
$$ 0 \le g(n) \le d h(n) $$
Collectively, the two inequalities imply that
$$ 0 \le f(n) \le cd h(n) $$
Thus, it is the case tha t\( f(n) = \BigO{h(n)} \).
This means,
$$ f(n) = \BigO{g(n)} \text{ and } g(n) = \BigO{h(n)} \text{ imply } f(n) = \BigO{h(n)} $$
Similar transitive can be derived for the other asymptotic bounds. We list them here.
$$ f(n) = \Omega(g(n)) \text{ and } g(n) = \Omega(h(n)) \text{ imply } f(n) = \Omega(h(n)) $$
$$ f(n) = \theta(g(n)) \text{ and } g(n) = \theta(h(n)) \text{ imply } f(n) = \theta(h(n)) $$
$$ f(n) = \smallo{g(n)} \text{ and } g(n) = \smallo{h(n)} \text{ imply } f(n) = \smallo{h(n)} $$
$$ f(n) = \omega(g(n)) \text{ and } g(n) = \omega(h(n)) \text{ imply } f(n) = \omega(h(n)) $$