$f(n) = O(n) \overset ? \implies \log(f(n)) = O(\log n)$

Question

I have been trying to find a counter-example to prove this is false. However, I feel that I am going in the wrong direction (all logs. are assumed to be in base $2$.) $$f(n) = O(n) \overset ? \implies \lg(f(n)) = O(\lg n).$$ This is my work so far to tackle this: \begin{align} 0 &\leq \log(f(n)) \leq c \cdot \log(n) \\ 0 &\leq f(n) \leq n^c \end{align}

It looks to me that this would always be true (when $f(n)$ is increasing and positive.) But I still don't know where to go from here. Any help would be greatly appreciated.

Thanks in advance.

Answer 1

Do it the other way.

If: $$0 \le f(n) \le c n$$

Then, since $\ln$ is a monotone increasing function, hence for sufficiently large $f(n)$: $$0 \le \ln{(f(n))} \le \ln{(cn)} = \ln{c} + \ln{n}$$

Since $\ln{c}$ is a constant, clearly we have $\ln{(f(n)})$ in $O(\ln n)$.

Answer 2

Better to work straightforward from the given conditions:

$0 \le f(n) \le c * n$ implies $\log{(f(n))} \le \log{(c * n)} = \log({c}) + \log({n}) \leq c * \log({n})$

Therefore, $\log(f(n)) = O(\log({n}))$ by using the same $c$ constant