How do I prove or refute the statement $f(n) = O(f(n/2))$? I need to prove(or refute) the following asymptotic statement: $f(n) = O(f(n/2))$. I am not sure, but the only thing that came in my mind so far, is that we can precisely pick such an element for example $2n$, so the statement will be correct: $2n = O(n)$. Unfortunately, i really think that my assumption is wrong and it doesn't hold for all $n$ and $c$. So i want you to help me either to prove or refute the statement.

I will interpret your question as follows.

> Denote by $F$ the set of all strictly increasing, strictly positive, real-valued functions that are defined on $\mathbb{R}$. Is it true that, for all $f \in F$, the following holds: $$ \limsup_{x\rightarrow\infty}\frac{f(x)}{f(x/2)} < \infty? \tag{*}\label{eq} $$

The answer to this question is: "No, \eqref{eq} doesn't hold for all $f \in F$." As a counter-example take, for instance, the exponential function. Indeed, $$ \limsup_{x\rightarrow\infty} \frac{e^x}{e^{x/2}} = \limsup_{x\rightarrow\infty} e^{x/2} = \infty. $$