FIBONACCI NUMBER

Leetcode Problem #509

Problem statement

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F(0) = 0
F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.

Given n, calculate F(n).

JAVA CODE FIBONACCI NUMBER

Recursion solution for Fibonacci Number

class Solution {
    public int fib(int n) {
        if(n == 0 || n == 1){
            return n;
        }
        return fib(n-1) + fib(n-2);
    }
}

Complexity issue

• This function uses recursion to compute the Fibonacci number at the nth position.
• Note that this implementation has an exponential time complexity and is not efficient for large n due to repeated calculations.
• For larger inputs, consider using iterative solutions or memoization to optimize the computation.

Iteration solution for Fibonacci Number

• It avoids the overhead of repeated function calls.
• Time Complexity: O(n)
• Space Complexity: O(1)

class Solution {
    public int fib(int n) {
        if(n == 0 || n == 1){
            return n;
        }

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

        return c;
    }
}

Memoization solution for Fibonacci Number

• Memoization stores the results of expensive function calls and reuses the stored results, when the same inputs occur again.
• This technique is particularly useful in Dynamic Programming (DP).
• Time Complexity: O(n)
• Space Complexity: O(n) (due to the map storing intermediate results)

import java.util.HashMap;
import java.util.Map;

class Solution {
    private Map <Integer, Integer> mem = new HashMap<>();
    public int fib(int n) {
        if(n == 0 || n == 1){
            return n;
        }
        if (mem.containsKey(n)) {
            return mem.get(n);
        }  
        
        int result = fib(n-1) + fib(n-2);
        mem.put(n, result);
        return result;
    }
}

Both of these approaches are more efficient than the naive recursive solution, especially for large values of n.

Golang Solution Using Memoization

//DP Fibonacci number-1 
// 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ....

package main

import (
	"fmt"
)

func fibonacci(num int, memo map[int]int) int {

	if num <= 1 {
		return num
	}

	if memo[num] != 0 {
		return memo[num]
	}

	memo[num] = fibonacci(num-1, memo) + fibonacci(num-2, memo)
	return memo[num]
}

func main() {
	memo := map[int]int{}
	fmt.Printf("%d\n", fibonacci(50, memo))
	fmt.Printf("%d\n", fibonacci(5, memo))
}


//Output
//12586269025
//5

//Program exited.

Summary

• Time Complexity: O(n)
• Space Complexity: O(n)

This memoized approach is much more efficient than the naive recursive Fibonacci implementation, which has a time complexity of O(2ⁿ)

Golang Solution Using Bottom up approach

//DP Fibonacci number-1
// 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ....

package main

import (
	"fmt"
)

func fibonacci(num int, memo map[int]int) int {
	memo[0] = 0
	memo[1] = 1

	for i := 2; i <= num; i++ {
		memo[i] = memo[i-1] + memo[i-2]
	}

	return memo[num]
}

func main() {
	memo := map[int]int{}
	fmt.Printf("%d\n", fibonacci(50, memo))
	fmt.Printf("%d\n", fibonacci(5, memo))
}

//Output
//12586269025
//5

//Program exited.

The complexity of this bottom-up dynamic programming (DP) Fibonacci code is as follows:

Time Complexity

The time complexity of this bottom-up approach is O(n).

• The function iterates once from 2 to num, performing a constant-time addition operation at each iteration.
• Since there’s only one loop that executes n−1n – 1n−1 times, the time complexity is O(n).

Space Complexity

The space complexity is also O(n).

• The function uses a map memo to store Fibonacci numbers up to num, which requires O(n) space.

Golang Solution Using Bottom up approach V2

//DP Fibonacci number-1
// 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ....

package main

import (
	"fmt"
)

func fibonacci(num int, memo map[int]int) int {
	a := 0
	b := 1
	c := 0

	for i := 2; i <= num; i++ {
		c = a + b
		a = b
		b = c
	}

	return c
}

func main() {
	memo := map[int]int{}
	fmt.Printf("%d\n", fibonacci(50, memo))
	fmt.Printf("%d\n", fibonacci(5, memo))
}

//Output
//12586269025
//5

//Program exited.

Complexity Analysis

Time Complexity

• Like the previous approaches, the time complexity remains O(n), since there is a single loop that iterates from 2 to num.

Space Complexity

• Space Complexity: O(1)
  • Unlike the previous implementations, this approach only uses three variables (a, b, and c), requiring constant space regardless of the input size.

Comparison with the Top-Down (Memoized Recursive) Approach

Similarities:

• Time Complexity: Both approaches have O(n) time complexity, as each Fibonacci number up to num is calculated only once.
• Space Complexity: Both require O(n) space for storing the Fibonacci sequence values.

Differences:

• Recursion vs. Iteration:
  • The top-down approach uses recursion and memoization. This can lead to a deeper call stack, with a maximum recursion depth of num, which might be a disadvantage if num is very large, as it could risk a stack overflow.
  • The bottom-up approach avoids recursion altogether by using iteration, making it more efficient in terms of stack space and less prone to stack overflow.
• Efficiency:
  • The bottom-up approach has lower overhead since it avoids recursive calls and directly iterates to build the solution, making it slightly faster in practice due to the absence of function call overhead.

Summary

• Top-Down (Recursive with Memoization):
  • Time Complexity: O(n)
  • Space Complexity: O(n) (due to memoization and recursion stack)
  • Potentially more stack overhead and risk of stack overflow.
• Bottom-Up (Iterative with Memoization):
  • Time Complexity: O(n)
  • Space Complexity: O(n) (due to memoization)
  • More efficient in practice with no recursion overhead and lower risk of stack overflow.
  • We have to solve subproblem in topological sort order.
• V2 Optimized Bottom-Up Approach:
  • Time Complexity: O(n)
  • Space Complexity: O(1)
  • Most efficient in terms of both time and space, as it uses only constant space and avoids recursion altogether.

For practical purposes, the bottom-up approach is generally preferred for its simplicity and efficiency.

Visit Previous Problem#1

Visit Previous Problem#2

Similar Questions

• Climbing Stairs
• Split Array into Fibonacci Sequence
• Length of Longest Fibonacci Subsequence
• N-th Tribonacci Number