Is it true that every function f satisfies $f(2n) = Θ(f(n))$?

Question

I am trying to determine if this statement is correct or not:

Every function f satisfies f(2n) = Θ(f(n))

Where, as I understand it, $f(2n)$ cannot be bounded by $f(n)$, as:

f(n) ≤ f(2n)

Since $2n$ is twice that of $n$, making me think that simply by definition of being multiplied by $2$, it will encapsulate $f(n)$.

So does this mean that $f(2n)$ cannot be bounded by $f(n)$, (since something cannot be bounded by the thing it is already greater than?)

Answer 1

Hint: Let $f(x)=2^x$. The function $2^{2n}$ grows far faster than $2^n$.

Answer 2

Well, first off: there's no reason to suspect that $f(2n)\geq f(n)$. Take, for instance, $f(x)=\frac{1}{x}$ (or any other function which is decreasing).

To say that $f(2n)=\Theta(f(n))$ means that $f(2n)$ is eventually bounded on both sides by constant multiples of $f(n)$. So, to disprove this result, you would need to find a function which grows (much) faster and faster as $n\to\infty$.

Answer 3

Look up the definition of $\Theta$. The requirement $f(2n)=\Theta(f(n))$ says $k_1f(n) \le f(2n) \le k_2f(n)$ For $f(n)=3n$, this is correct-take $k_1=2, k_2=4$. For $f(n)=x^2$ it is still true-take $k_1=1, k_2=5$. But for $f(n)=2^n...$