Class Fibonacci

java.lang.Object
topics.divideconquer.Fibonacci
public class Fibonacci extends Object
Fibonacci Number Calculation using Divide and Conquer and Iterative Approaches. Problem Definition: Calculate the n-th Fibonacci number where: F(0) = 0 F(1) = 1 F(n) = F(n-1) + F(n-2) for n >= 2 Fibonacci Series Example: F(0)=0, F(1)=1, F(2)=1, F(3)=2, F(4)=3, F(5)=5, F(10)=55, F(11)=89 This class demonstrates TWO iterative solutions, both O(n). Why only iterative here? The naive recursive approach is exponential O(2^n), making it impractical for larger n. See topics.dynamic.Fibonacci for Dynamic Programming approaches that handle large n efficiently. Complexity Comparison: - fib1() Iterative: Time O(n), Space O(1) - best space efficiency - fib2() Iterative+array: Time O(n), Space O(n) - stores all intermediate results - Naive Recursive: Time O(2^n), Space O(n) - too slow for large n - Dynamic Programming: Time O(n), Space O(n) - best for large n Why Naive Recursion Fails: fib(5) calls fib(4) and fib(3); fib(4) calls fib(3) and fib(2); fib(3) is calculated twice, fib(2) three times! For fib(40): 300+ million recursive calls (takes minutes). With fib1(): 40 operations (microseconds). When to Use Each Method: - fib1(): When you only need the final result and want minimal memory - fib2(): When you need all intermediate Fibonacci numbers or want a cache - Dynamic Programming: For very large n (n > 10^6) or when optimization is critical
Author:
vicegd
See Also:

  • Constructor Summary

    Constructors
    Constructor
    Description
    Fibonacci()
     

  • Method Summary

    Modifier and Type
    Method
    Description
    int
    fib1(int n)
    Calculates the n-th Fibonacci number using space-optimized iteration.
    int
    fib2(int n, int[] v)
    Calculates the n-th Fibonacci number using dynamic programming with a memoization array.
    int
    fib3(int n)
    First recursive version, with a linear complexity O(n).
    int
    fib4(int n)
    Second recursive version, with equation T(n)=T(n-1)+T(n-2)+O(1), that once solved is exponential O(1.6^n).
    int
    fib5(int n)
    DandC sophisticated solution that is O(log n).

    Methods inherited from class Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • Fibonacci

      public Fibonacci()

  • Method Details

    • fib1

      public int fib1(int n)
      Calculates the n-th Fibonacci number using space-optimized iteration. Algorithm - Two-Variable Rolling Window: Keep track of only the two most recent Fibonacci numbers: n1: F(i-1) n2: F(i) Each iteration: sum = n1 + n2, then shift: n1 = n2, n2 = sum Example Trace for fib1(5): Initial: n1=0, n2=1 i=1: sum=1, n1=1, n2=1 i=2: sum=2, n1=1, n2=2 i=3: sum=3, n1=2, n2=3 i=4: sum=5, n1=3, n2=5 Return: n1=5 (correct) Complexity Analysis: - Time: O(n) - single loop from 1 to n - Space: O(1) - only two variables needed Why This is Better Than Naive Recursion: Naive fib(50): ~1.1 billion recursive calls, 30+ seconds This fib1(50): 50 additions, microseconds -> 1,000,000x faster
      Parameters:
      n - the position in Fibonacci sequence (n >= 0)
      Returns:
      the n-th Fibonacci number
      Throws:
      IllegalArgumentException - if n invalid input: '<' 0

    • fib2

      public int fib2(int n, int[] v)
      Calculates the n-th Fibonacci number using dynamic programming with a memoization array. Algorithm - Array-Based Iteration (Classical DP): Store all calculated Fibonacci numbers in array v[]: v[0] = 0 v[1] = 1 v[i] = v[i-1] + v[i-2] for i >= 2 Example Trace for fib2(5, array): v[0] = 0 v[1] = 1 v[2] = 0 + 1 = 1 v[3] = 1 + 1 = 2 v[4] = 1 + 2 = 3 v[5] = 2 + 3 = 5 invalid input: '<'- return value Complexity Analysis: - Time: O(n) - iterates from 2 to n - Space: O(n) - requires array of size n+1 Advantages over fib1(): - Easy to understand (classic DP pattern) - Can retrieve any F(i) from the array without recalculation - Good for educational demonstration of DP Disadvantages compared to fib1(): - Uses O(n) extra space instead of O(1) - If only F(n) is needed, fib1() is better When to Use fib2(): - When you need all intermediate Fibonacci numbers F(0) to F(n) - When teaching Dynamic Programming concepts
      Parameters:
      n - the position in Fibonacci sequence to calculate (n >= 0)
      v - array to store computed Fibonacci values; must have length >= n+1
      Returns:
      the n-th Fibonacci number (same as v[n])
      Throws:
      ArrayIndexOutOfBoundsException - if v.length invalid input: '<'= n
      NullPointerException - if v is null

    • fib3

      public int fib3(int n)
      First recursive version, with a linear complexity O(n). It is DandC by subtraction with a=1,b=1,k=0 - O(n)
      Parameters:
      n - Positive number to be used as input
      Returns:
      Fibonacci value for n

    • fib4

      public int fib4(int n)
      Second recursive version, with equation T(n)=T(n-1)+T(n-2)+O(1), that once solved is exponential O(1.6^n). IN SHORT, THIS IS AN UNAFFORDABLE SOLUTION
      Parameters:
      n - Positive number to be used as input
      Returns:
      Fibonacci value for n

    • fib5

      public int fib5(int n)
      DandC sophisticated solution that is O(log n). It is DandV by division with a=1,b=2,k=0 and it is programmed in an iterative way.
      Parameters:
      n - Positive number to be used as input
      Returns:
      Fibonacci value for n