Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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))$.
