The O(n) Club: Fibonacci Number: Attack of the Useless Recursion

The O(n) Club: Fibonacci Number—Attack of the Useless Recursion

⚡ TL;DR

If you’re asked for the nth Fibonacci number, please do not set your CPU on fire with recursion. Just use two variables, pretend you’re shuffling mugs at a hackathon, and loop through. Here’s how Java would do it if it drank less coffee:

// O(n) time, O(1) space
int fib(int n) {
    if (n < 2) return n;
    int a = 0, b = 1;
    for (int i = 2; i <= n; i++) {
        int c = a + b;
        a = b;
        b = c;
    }
    return b;
}

🧠 How Devs Usually Mess This Up

You’re in the interview. You panic. You remember recursion is a thing. So you write fib(n-1) + fib(n-2) like you’re implementing ancient legend. Works for tiny n, but for anything above coffee break numbers, your laptop fans become helicopters and your interviewer’s faith in humanity wavers. Welcome to O(2ⁿ)—where the call stack and your confidence go to die. Sure, memoization helps, but when n is up to 30, this is all just… unnecessary cardio for your computer.

🔍 What’s Actually Going On

The Fibonacci sequence was invented to model rabbits breeding—basically, exponential bunny chaos. In reality, all you need are the last two answers at every step: oldValue, newValue, add them up, move on. Like swapping two sticky notes every minute, not keeping the entire history since the beginning of rabbits. This is O(n) time and O(1) space—concise, efficient, and delightfully unacrobatic. Unless you want to flex with Binet’s Formula (floating point errors love it), just loop and don’t look back.

🛠️ PseudoCode

• Bail for base cases:
  If n is 0 or 1, just give n back. No drama.
• Track just two numbers:
  Start with a = 0, b = 1. Keep them as your current and next rabbit count.
• Iterate up to n:
  For i from 2 up: add a + b, assign to c, then move a up to b, b up to c. Rinse, repeat.
• Return b.
  It contains the nth Fibonacci—no rabbits, no lag, all glory.

💻 The Code

public class Solution {
    public int fib(int n) {
        if (n < 2) return n;
        int a = 0, b = 1;
        for (int i = 2; i <= n; i++) {
            int c = a + b;
            a = b;
            b = c;
        }
        return b;
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Recursion is a CPU furnace: For n > 20, you’ll waste power and recruiter admiration. Save that for mining Bitcoin.
• Closed-form (Binet’s Formula): Floating point math is secretly plotting against you. For small n (<=30), you gain nothing but headaches.
• Arrays? Why: Using a full DP array here is like bringing a database to a coin toss.
• Complexity check: Iterative or DP: O(n) time. Iterative, two vars: O(1) space. Recursion: O(2ⁿ) time, O(n) stack—may the odds be ever in your JVM’s favor.

🧠 Interviewer Brain-Tattoo

“If your Fibonacci needs floating point math, somewhere, a bunny cries and a CS professor spills their coffee.”