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  )

Advertisements

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 )
 * @link    https://quickgrid.wordpress.com
 */

#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] = 0;
    F[1] = 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 )
 * @link    https://quickgrid.wordpress.com
 */

#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] = 0;
    F[1] = 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;
}