Fibronacci

Input: 10

Output: 55

package jan27;

public class Fibronacci {
    public static void main(String[] args) {
        int n = 10;
        System.out.println(fibronacci(n));  // EXPECTATION
    }

    // Time Complexity: O(2^n)
    // Space Complexity: O(n) [due to recursive call stack]
    private static int fibronacci(int n) {
        if (n <= 1) return n;               // BASE CASE

        int preOrder = fibronacci(n - 1);   // FAITH
        int postOrder = fibronacci(n - 2);  // FAITH

        return preOrder + postOrder;           // WORK
    }
}

🔍 Explanation:
✅ Time Complexity: O(2^n)
The function makes two recursive calls at each step.
This creates a binary tree of calls with height n.
The total number of function calls grows exponentially, hence O(2^n).
✅ Space Complexity: O(n)
Although there are many calls, the recursive call stack depth goes up to n in the worst case.
So the space used by the stack is linear.



Case
Time Complexity
Space Complexity
Notes




Best
O(2ⁿ)
O(n)
No memoization; exponential recursive calls


Average
O(2ⁿ)
O(n)
Same as worst, as all calls happen


Worst
O(2ⁿ)
O(n)
Deepest stack with overlapping subproblems