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
I'm assuming you're looking for the lower bound of the computational complexity of computing the fibonacci sequence in the naive way. Correct?
Yes
I can easily see \(2^n\), but I'm not sure how they got to \(2^{n-1}\).
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)
It's \(2^{n/2}\)? Hmmmm....
That's what the problem suggests
Are you given any details of the naive implementation?
Fibonacci(n) {n>=0} if n<=1 then return (n); else a := Fibonacci(n - 2); b := Fibonacci(n - 1); return (a + b) endif
Are you sure it's \(\displaystyle2^{n/2}\) and not \(\displaystyle\frac{2^n}{2}\)?
yes I'm sure that it says \[\Omega(2^{n/2})\]
I'm really not sure. I keep running into some issue that I can't navigate around.
Perhaps @asnaseer might be able to help out more.
Could you tell me what was the issue you ran into exactly?
sorry guys - I never did analysis of algorithms...
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.
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.
Join our real-time social learning platform and learn together with your friends!