Prove or disprove $f(n) = O(f(2n))$

418 Views Asked by At

I wonder how to to prove or disprove that $f(n) = O(f(2n))$

I have tried many function, and think it is right, but still don't have any idea how to prove.

Could anyone give me a hint about it?

1

There are 1 best solutions below

0
On

If \begin{equation} f(n)=\begin{cases}1 & n\text{ even,}\\ n& n\text{ odd,}\end{cases} \end{equation} then \begin{equation} \mathcal{O}(f(2n))=\mathcal{O}(1)\text{,} \end{equation} but $f(n)$ is not asymptotically constant.