## 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  )

## Fibonacci Memoization Top Down ( Recursive ) and Bottom Up ( Iterative )

Fibonacci Memoization Top Down ( Recursive ) and Bottom Up ( Iterative ) Dynamic Programming:

### Top Down Fibonacci Memoization Code:

```/**
* @author  Quickgrid ( Asif Ahmed )
*/

#include<stdio.h>

#define N 64
long long F[N];

/**
* Top Down Recursive Fibonacci Memoization
*/
long long topDownMemFib(long long n){
/**
* If its not 1 then it means there is already a calculated value
* So no more need to compute, just return that value
*/
if(F[n] != -1)
return F[n];

F[n] = topDownMemFib(n - 1) + topDownMemFib(n - 2);
return F[n];
}

int main(){
register unsigned i;

unsigned n;
printf("Enter a number:\n");
scanf("%u", &n);

/**
* Terminating condition values
*/
F = 0;
F = 1;

/**
* First set the whole array to -1, means there are no calculated value
*/
for(i = 2; i <= n; ++i)
F[i] = -1;

printf("%lld\n", topDownMemFib(n));

return 0;
}
```

### Bottom Up Iterative Fibonacci Implementation:

```/**
* @author  Quickgrid ( Asif Ahmed )
*/

#include<stdio.h>

/**
* Increase this value for numbers more than 64
*/
#define N 64
long long F[N];

/**
* Top Down Fibonacci Memoization
*/
long long bottomUpMemFib(long long n){
/**
* Terminating Condition
*/
F = 0;
F = 1;

register unsigned i;
for(i = 2; i <= n; ++i)
F[i] = F[i - 1] + F[i - 2];

return F[n];
}

int main(){
register unsigned i;

unsigned n;
printf("Enter a number:\n");
scanf("%u", &n);

printf("%lld\n", bottomUpMemFib(n));

return 0;
}
```