# Prove or disapprove the statement: $f(n)=\Theta(f(\frac{n}{2}))$

Prove or disapprove the statement:

$$f(n)=\Theta(f(\frac{n}{2}))$$

where $f$ is an asymptotically positive function.

I have thought the following:

Let $f(n)=\Theta(f(\frac{n}{2}))$.Then $\exists c_1,c_2>0 \text{ and } n_0 \geq 1 \text{ such that } \forall n \geq n_0:$

$$c_1 f(\frac{n}{2}) \leq f(n) \leq c_2 f(\frac{n}{2})$$

Let $f(n)=2^n$.Then:

$$c_1 2^{\frac{n}{2}} \leq 2^n \leq c_2 2^{\frac{n}{2}} \Rightarrow c_1 \leq 2^{\frac{n}{2}} \leq c_2$$

$$2^{\frac{n}{2}} \leq c_2 \Rightarrow 2^n \leq c_2^2 \Rightarrow n \leq \lg c_2^2 \text{ Contradiction}$$

Could you tell me if it is right?

• It's true for some functions but not for others. Your counterexample is perfect. – Antonio Vargas Jul 13 '14 at 18:48
• Great!!!Thank you very much!!! – evinda Jul 13 '14 at 18:51
• In the future just use the (asymptotics) tag. No need for the "big-o-notation" tag. – Antonio Vargas Jul 14 '14 at 6:24
• @AntonioVargas A ok!!!I will take it into consideration!!! :) – evinda Jul 14 '14 at 14:32

## 2 Answers

As mentioned in the comments, your work is correct (and thus the original proposition is false).

Just set $f=f(n) = 2^{\frac{n}{2}}, \ g=g(n) = 2^n$ and take $\lim_n \frac{f}{g} = 0$, so $f <c_1 g \ \forall \ c_1>0$ and $n>n_0$ or simply $f=o(g)$. Clearly $\lim_n \frac{g}{f} = \infty$, so LHS of the inequality is never fulfilled: $\not \exists c_2 \ \text{s.t.} f>c_2g \ \forall n>n_0$ or simply $g=\omega(f)$.