Fibonacci Sequence Dynamic Programming | From Exponential time to Linear time to Constant Time Solution

fibonacci.cpp

#include<bits/stdc++.h>
using namespace std ; 

// Nth number of FIBONACCI SEQUENCE
// Bruteforce = 2^n , O(1) space
// Top down = O(N) Time , O(N) space
// Bottom up = O(N) Time , O(1) Space
// Math Solution = O(1) Time and Space

int totalCalls = 0 ; 

int cache[100] ; 
int fibTop(int n ){
    totalCalls++ ; 

    if(cache[n]>0) return cache[n] ; 

    if(n<=1) return n  ; 
    cache[n] =  fib(n-1) + fib(n-2) ;  
    return cache[n] ; 
}

int fibBottom(int n ){
    int a = 0 ; 
    int b = 1 ; 
    int c = a+b ; 
    for(int i = 2 ; i<=n ; i++){
        c = a+b ; 
        a = b; 
        b = c ; 
        totalCalls++ ; 
    }
    return c ; 
}

int fibMath(int n ){
  double phi = (1 + sqrt(5)) / 2; 
  return round(pow(phi, n) / sqrt(5)); 
}

int main(void){
    cout<< fibMath(32) <<endl; 
    cout<<totalCalls<<endl; 
}