Lower Bound of Fibonacci Big Omega Time Complexity

Lower Bound of Fibonacci Big Omega Time Complexity:

Code for Recursive Fibonacci Algorithm:

```int fib(int n){
if (n < 2)
return n;
else
return fib(n - 1) + fib(n - 2);
}
```

Time Complexity Lower Bound ( Big Omega ):

Detailed explanation for calculating the upper and lower bound can be found here.

```T(n) =  T(n-1) + T(n-2) + c
=  T(n-2) + T(n-3) + c + T(n-2) + c
=  2T(n-2) + T(n-3) + 2c
>= 2T(n-2) + 2c
=  2T(n-3) + T(n-4) + c) + 2c
=  2T(n-3) + 2T(n-4) + 2c + 2c
=  2T(n-3) + 2T(n-4) + 4c
=  2T(n-4) + 2T(n-5) + 2c + 2T(n-4) + 4c
=  4T(n-4) + 2T(n-5) + 6c
>= 4T(n-4) + 6c
=  4T(n-5) + 4T(n-6) + 10c
=  4T(n-6) + 4T(n-7) + 4c + 4T(n-6) + 10c
=  8T(n-6) + 4T(n-7) + 14c
>= 8T(n-6) + 14c
=  .......................
=  .......................
=  2^k T(n - 2k) + (2^(k+1)-2)c

for, k steps, n - 2k = 0 or, 1 the recursion stops
=> n = 2k
=> k = n / 2

so, from the recurrence relation
= 2^(n/2) * T(0) + (2^((n/2) +1) -2) * c
= 2^(n/2) * c + (2^((n/2) +1) -2) * c
= Ω(2^(n/2))
```

So, the lower bound of for this recursive Fibonacci algorithm implementation is Big Omega of 2n / 2.

Lower Bound:  Ω ( 2n / 2  )