True or false: If log f (n) ∈ Θ(log g(n)), then f (n) ∈ Θ(g(n)).

Question

It seems true and I can find cases that satisfy this statement. But how to formally prove it? Thank you.

Answer 1

The statement is false.

---

Try proving it by unfolding the definitions. From $$c'·\log g≤ \log f ≤ c·\log g \quad\text{eventually}$$ (with some $c, c' > 0$), by applying $\exp$, you get $$g^{c'} ≤ f ≤ g^c\quad\text{eventually}.$$ If $c = c' = 1$, everything seems fine. But what if not?

---

Counterexample. Say $f = \operatorname{id}_ℕ$ and $g (n) = n^2$ (so $g = f·f$). Then $\log g = 2 \log f$, but $f \notin Θ(g)$.