$f(n)=\Theta(f(n/2))$. Prove or disprove.

15.9k Views Asked by At

I am trying to prove that the statement $f(n)=\Theta(f(n/2))$ is true. This is what I have so far. I am not sure it is correct.

Assume $f(n)=\Theta(f(\frac{n}{2}))$. Then $f(n)=O(f(\frac{n}{2}))$ and $f(n)=\Omega(f(\frac{n}{2}))$.

$f(n)=\Theta(f(\frac{n}{2}))$ means that there is a constant $c$ for which $f(n)\le c \cdot f(\frac{n}{2})$. $f(n)=\Omega(f(\frac{n}{2}))$ means that there is a constant $c'$ for which $f(n) \ge c' \cdot f(\frac{n}{2})$.

Is this enough for the proof?

1

There are 1 best solutions below

2
On BEST ANSWER

The "proof" seems to be saying, in effect, "Assume $f(n) = \Theta(f(n/2))$. Then it follows that $f(n) = \Theta(f(n/2))$."

Try $f(n) = e^n$. Is the theorem true in that case?