0
$\begingroup$

In asymptotic notation the transivity holds, however what happens when we have small o such as if f(n)= o(h(n)) does that means that also g(n)=o(h(n)) holds?

i take as granted that both of f(n)=o(h(n)) is true and f(n)= O(g(n)) (from THETA) then i need to show g(n) < c h(n) given that i have f(n) <= d g(n) and f(n) < c h(n) how one would proceed from there?

$\endgroup$
0
$\begingroup$

From $f(n) = \Theta(g(n))$ you know that, for some positive constants $c \in \mathbb{R}^+$ and $\eta \in \mathbb{N}$, and for all $n \ge \eta$, it holds that $f(n) \ge c g(n)$, i.e., $g(n) \le \frac{1}{c} f(n)$.$^1$

Moreover, from $f(n) = o(h(n))$, you know that for any constant $c' > 0$ there is some $\eta'_{c'}$ such that $f(n) \le c' h(n)$ for any $n \ge \eta'_{c'}$.

Pick any constant $c'' > 0$ and let $\eta'' = \max\{\eta, \eta'_{c'}\}$ where $c' = c \cdot c'' > 0$. From the previous inequalities we have that, for any $n \ge \eta''$: $$ g(n) \le \frac{1}{c} f(n) \le \frac{1}{c} \cdot c' h(n) = c'' h(n), $$ thus proving that $g(n) = o(h(n))$.


$^1$: In fact, the weaker condition $f(n) = \Omega(g(n))$ suffices.
$\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.