How can I prove that the lower bound of the naive fibonacci sequence implementation is 2^(n/2)? I think it should be by induction, but I'm super bad with induction

Question

kinggeorge · Answer

I'm assuming you're looking for the lower bound of the computational complexity of computing the fibonacci sequence in the naive way. Correct?

anonymous · Answer

Yes

kinggeorge · Answer

I can easily see $2^n$, but I'm not sure how they got to $2^{n-1}$.

anonymous · Answer

I know that the tight bound is 2^n which means big omega is also so but I can't figure out how it is also big omega of 2^(n/2)

kinggeorge · Answer

It's $2^{n/2}$? Hmmmm....

anonymous · Answer

That's what the problem suggests

kinggeorge · Answer

Are you given any details of the naive implementation?

anonymous · Answer

Fibonacci(n)
{n>=0}
if n<=1 then return (n);
else
a := Fibonacci(n - 2);
b := Fibonacci(n - 1);
return (a + b)
endif

kinggeorge · Answer

Are you sure it's $\displaystyle2^{n/2}$ and not $\displaystyle\frac{2^n}{2}$?

anonymous · Answer

yes I'm sure that it says $$\Omega(2^{n/2})$$

kinggeorge · Answer

I'm really not sure. I keep running into some issue that I can't navigate around.

kinggeorge · Answer

Perhaps @asnaseer might be able to help out more.

anonymous · Answer

Could you tell me what was the issue you ran into exactly?

asnaseer · Answer

sorry guys - I never did analysis of algorithms...

kinggeorge · Answer

I started looking at the steps required to compute Fibonacci(n) using the short little program you wrote out. It turns out you get the fibonacci numbers themselves. So to show it was in $\Omega(2^{n/2})$ I took the limit $$\lim_{n\to\infty}\frac{F_n}{2^{n/2}}$$As far as I can tell, this goes to infinity.

kinggeorge · Answer

You don't actually get the fibonacci numbers, you actually get something slightly bigger, meaning that if the above limit goes to infinity, the actual limit I need to evaluate would also go to infinity since it's always greater.