Skip to content

Instantly share code, notes, and snippets.

@valarpirai

valarpirai/Fibonacci.java

Last active October 24, 2025 05:26
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save valarpirai/b66992a36b50c8f77f5c2040f2fcd8d2 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save valarpirai/b66992a36b50c8f77f5c2040f2fcd8d2 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. valarpirai revised this gist Oct 24, 2025. 1 changed file with 2 additions and 0 deletions.
    2 changes: 2 additions & 0 deletions Fibonacci.java
    View file
    Original file line number Diff line number Diff line change
    @@ -1,4 +1,5 @@
    public class Fibonacci {
    // Recursive approach without optimizations
    // Recursive: O(2^n) time, O(n) space
    public static long fibonacciRecursive(int n) {
    return n <= 1 ? n : fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
    @@ -33,5 +34,6 @@ public static void findFib(int n) {
    public static void main(String[] args) {
    findFib(10);
    findFib(45);
    // findFib(100); - I will never call this method with recursive approach
    }
    }
  2. valarpirai created this gist Oct 24, 2025.
    37 changes: 37 additions & 0 deletions Fibonacci.java
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,37 @@
    public class Fibonacci {
    // Recursive: O(2^n) time, O(n) space
    public static long fibonacciRecursive(int n) {
    return n <= 1 ? n : fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
    }

    // Iterative: O(n) time, O(1) space
    public static long fibonacciIterative(int n) {
    if (n <= 1) return n;
    long prev = 0, curr = 1;
    for (int i = 2; i <= n; i++) {
    long next = prev + curr;
    prev = curr;
    curr = next;
    }
    return curr;
    }

    public static void findFib(int n) {
    long start = System.nanoTime();
    long iterative = fibonacciIterative(n);
    double iterativeTime = (System.nanoTime() - start) / 1_000_000.0;

    System.out.printf("Iterative (n=%d): %d, Time: %.3f ms%n", n, iterative, iterativeTime);

    start = System.nanoTime();
    long recursive = fibonacciRecursive(n);
    double recursiveTime = (System.nanoTime() - start) / 1_000_000.0;

    System.out.printf("Recursive (n=%d): %d, Time: %.3f ms%n", n, recursive, recursiveTime);
    }

    public static void main(String[] args) {
    findFib(10);
    findFib(45);
    }
    }