Class Fibonacci

java.lang.Object
topics.dynamic.fibonacci.Fibonacci
public class Fibonacci extends Object

Fibonacci Sequence

Computes the Fibonacci number of order N. This class serves as a masterclass in algorithmic complexity, demonstrating how the exact same mathematical problem can be solved using different paradigms, ranging from unaffordable exponential time to highly optimized logarithmic time.

Sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89...

Author:
vicegd

  • Constructor Details

    • Fibonacci

      public Fibonacci()

  • Method Details

    • fibonacciIterative

      public long fibonacciIterative(int n)

      1. Iterative Approach (Space Optimized DP)

      Computes Fibonacci using a simple loop. It only keeps track of the last two values instead of the entire array.

      • Time Complexity: O(N)
      • Space Complexity: O(1)
      Parameters:
      n - Positive integer input.
      Returns:
      Fibonacci value for n.

    • fibonacciDP

      public long fibonacciDP(int n)

      2. Dynamic Programming Approach (Tabulation)

      Uses a 1D array to store previously computed values, avoiding recalculations. This is the fundamental concept of Bottom-Up DP.

      • Time Complexity: O(N)
      • Space Complexity: O(N)
      Parameters:
      n - Positive integer input.
      Returns:
      Fibonacci value for n.

    • fibonacciTailRecursive

      public long fibonacciTailRecursive(int n)

      3. Tail Recursive Approach (Divide invalid input: '&' Conquer by Subtraction)

      A linear recursive version that passes the accumulators forward. Modern compilers can optimize this to prevent StackOverflows.

      • Time Complexity: O(N)
      • Space Complexity: O(N) (Call stack)
      Parameters:
      n - Positive integer input.
      Returns:
      Fibonacci value for n.

    • fibonacciNaiveRecursive

      public long fibonacciNaiveRecursive(int n)

      4. Naive Recursive Approach (The Trap)

      Strict translation of the mathematical formula F(n) = F(n-1) + F(n-2). It solves the same overlapping subproblems millions of times.

      • Time Complexity: Exponential O(1.618^N) - UNAFFORDABLE FOR N > 45.
      • Space Complexity: O(N) (Call stack)
      Parameters:
      n - Positive integer input.
      Returns:
      Fibonacci value for n.

    • fibonacciLogarithmic

      public long fibonacciLogarithmic(int n)

      5. Logarithmic Approach (Fast Doubling / Matrix Exponentiation)

      Sophisticated Divide invalid input: '&' Conquer algorithm that exploits mathematical matrix identities to compute the answer skipping massive amounts of steps.

      • Time Complexity: O(log N)
      • Space Complexity: O(1)
      Parameters:
      n - Positive integer input.
      Returns:
      Fibonacci value for n.