I understand that many similar questions of this sort have been asked, but in this case, the solution does not appear to be provable - or is it?

Question: If $f(n) = \Theta (g(n))$ and $g(n) = o(h(n))$ then $f(n) = O(h(n))$

Current solution:

$f(n) = \Theta (g(n))$ implies that $c_1 . g(n) \le f(n) \le c_2 . g(n)$ for $c_1, c_2 \in \mathbb{N}$ and $\forall n \ge k_1$ Call this equation $1$.

$g(n) = o(h(n))$ implies that $g(n) < c_3 . h(n) $ for $c_3 \in \mathbb{N}$ and $\forall n \ge k_1$ Call this equation $2$.

Multiply $2$ by $c_2$.

$c_2 . g(n) < c_2 . c_3 . h(n)$ Call this equation $3$.

From $1$ and $3$ it can be inferred that:

$f(n) \le c_2 . g(n) < c_2 . c_3 . h(n)$

Which means that $f(n) \not\le c_4 . h(n)$ (where $c_4 = c_2 . c_3$) and therefore $f(n) \not = O(h(n))$. Is this way of approaching the problem correct, or is it - as my intuition tells me - I've missed something entirely obvious?


Yes, it looks like that you missed something obvious.

A stronger claim: If $f(n) = \Theta (g(n))$ and $g(n) = o(h(n))$ then $f(n) = o(h(n))$.

Sketch of a proof: $f$ is bounded both above and below (up to a constant factor) by $g$ asymptotically, which is informally understood as $f$ and $g$ are the same asymptotically. $g$ is dominated by $h$ asymptotically. Hence $f$ is dominated by $h$ asymptotically.

(Sure, the above sketch is no more than rephrasing the claim in English. Well, that is how you (or at least I) would like to understand and reason about the situation)

Here is a detailed proof.

$f(n) = \Theta (g(n))$ implies that $c_1g(n) \le f(n) \le c_2 g(n)$ for some $c_1\gt0,\,c_2\gt0,\,k_1$ and any $n \gt k_1$.

$g(n) = o(h(n))$ implies that $|g(n)| < c_3 h(n) $ for some $c_3\gt0,\,k_2$ and any $n \gt k_2$.

Let $k_3=\max(k_1,k_2),\, c_4=\max(c_1,c_2)c_3\gt0$. Then for any $n\gt k_3$, $$\begin{align} |f(n)|&\le \max(|c_1g(n)|, |c_2g(n)|)\\ &\lt\max(c_1c_3h(n),c_2c_3h(n))\\ &=\max(c_1,c_2)c_3h(n)\\ &=c_4h(n) \end{align}$$ Note the first inequality above is guaranteed by the fact that $f(n)$ is bounded between $c_1g(n)$ and $c_2g(n)$ since $n>k_1$.

Finally, note that $f(n)=o(h(n))$ implies $f(n)=O(h(n))$.

P.S. There is some typo in your question. For example, "$c_1, c_2\in\mathbb{N}$" should be "some $c_1,\,c_2\in\Bbb{R}^+$" or "some $c_1>0,\,c_2>0$". If you let $f(n)=n, g(n)=2n$, then there is no natural number $c_1$ such that $c_1g(n)\le f(n)$ for even one positive $n$.

  • $\begingroup$ TL;DR Read the definitions first... $\endgroup$
    – R. Rengold
    Aug 25 '18 at 3:55

From $f(n) \le c_2 \cdot g(n) < c_2 \cdot c_3 . h(n)$ you can infer that $f(n) < c_4 \cdot h(n)$ with $c_4 = c_2 \cdot c_3$. Therefore $f(n) = o(h(n))$, and therefore also $f(n) = O(h(n))$, since this is a weaker statement (if $f(n) < c_4 \cdot h(n)$ is true, then certainly also $f(n) \le c_4 \cdot h(n)$ is).

Also notice, that you should be a little more precise with your formulations. $f(n) = \Theta(g(n))$ means, that there exist some $c_1, c_2 \in \mathbb{N}$ with ... The inequality doesn't hold for every choice of $c_1$ and $c_2$.


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.