Probar o desaprobar la declaración: $f(n)=\Theta(f(\frac{n}{2}))$

Question

Probar o desaprobar la declaración:

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

donde $f$ es una función asintóticamente positiva.

He pensado lo siguiente:

Que $f(n)=\Theta(f(\frac{n}{2}))$. Entonces $\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})$$

Que $f(n)=2^n$. A continuación:

$$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}$$

¿Podría decirme si es correcto?

Answer 1

Como se mencionó en los comentarios, tu trabajo es correcto (y por lo tanto es falsa la proposición original).

Answer 2

Solo conjunto $f=f(n) = 2^{\frac{n}{2}}, \ g=g(n) = 2^n$ y % tomar $\lim_n \frac{f}{g} = 0$, $f <c_1 g \ \forall \ c_1>0$ y $n>n_0$ o simplemente $f=o(g)$. Claramente $\lim_n \frac{g}{f} = \infty$, por lo que el lado izquierdo de la desigualdad no se cumple: $\not \exists c_2 \ \text{s.t.} f>c_2g \ \forall n>n_0$ o simplemente $g=\omega(f)$.