📅 Date: July 12, 2026
🧠 Mood: The Mathematician 📐
🔥 Topic: DSA Day 81: Fibonacci & Exponential Time Complexity
📉 The Nightmare of $O(2^N)$
Yesterday's linear recursion was forgiving. Today, I analyzed the Recursive Nth Fibonacci function, and it perfectly demonstrated why bad recursive code can completely freeze a modern processor.
The standard formula for Fibonacci is $F(N) = F(N-1) + F(N-2)$. Unlike a factorial which makes one call per level, this function branches into *two* calls at every single level.
🌳 The Branching Tree
If you draw out the execution tree for $F(5)$, it doesn't look like a straight line. It looks like a massive, expanding pyramid.
- Level 0: 1 call
- Level 1: 2 calls
- Level 2: 4 calls
- Level 3: 8 calls
The number of operations doubles at every step. This results in an Exponential Time Complexity of $O(2^N)$. This is horrific for performance. Trying to calculate $F(50)$ recursively will take your computer hours, if not days, to process. This is the exact reason Dynamic Programming exists—a topic I'll conquer later on the roadmap.
No comments:
Post a Comment