Class Fibonacci

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

Fibonacci Sequence

Computes the Fibonacci number of order N. This class focuses on demonstrating how the Divide and Conquer strategy can be applied to the same problem with drastically different performance outcomes (from Exponential to Logarithmic).

Author:
vicegd
See Also:

  • Constructor Details

    • Fibonacci

      public Fibonacci()

  • Method Details

    • fibonacciIterative

      public long fibonacciIterative(int n)

      1. Iterative Approach (Linear)

      Standard baseline approach for comparison.

      • Time: O(N)
      • Space: O(1)

    • fibonacciArray

      public long fibonacciArray(int n)

      2. Array-Based Approach (Memoization)

      Stores all intermediate results. (Primarily a Dynamic Programming concept).

      • Time: O(N)
      • Space: O(N)

    • fibonacciTailRecursive

      public long fibonacciTailRecursive(int n)

      3. Tail Recursive (Dinvalid input: '&C' by Subtraction)

      A linear recursive version. It divides the problem by subtracting 1 at each step, passing the accumulated state forward.

      • Time: O(N)
      • Space: O(N) (Call stack)

    • fibonacciNaiveRecursive

      public long fibonacciNaiveRecursive(int n)

      4. Naive Recursive (The Overlapping Trap)

      Strict translation of F(n) = F(n-1) + F(n-2). This is a classic example of when Divide and Conquer fails terribly because the subproblems are not independent, leading to massive recalculations.

      • Time: O(1.618^N) Exponential
      • Space: O(N) (Call stack)

    • fibonacciLogarithmic

      public long fibonacciLogarithmic(int n)

      5. Logarithmic Approach (Dinvalid input: '&C' by Division)

      Sophisticated Dinvalid input: '&C' algorithm that exploits mathematical matrix identities (Fast Doubling). It divides the problem size by 2 at each step instead of 1.

      • Time: O(log N)
      • Space: O(1)