Recursive Complexity Analysis

# CHAPTER 25

Recursive Complexity Analysis #

1. Introduction #

2. Learning Objectives #

• Define a Recurrence Relation formula (e.g., $T(n) = T(n-1) + c$).

• Map the horizontal and vertical bounds of a Recursive Tree.

• Analyze the $O(n)$ footprint of Single-Branch Recursion.

• Trace the catastrophic $O(2^n)$ explosion of Multi-Branch Recursion.

3. The Recurrence Relation #

The format is: $T(n) = a \cdot T(n / b) + O(k)$

• $a$ = How many times the function calls itself (The Branches).

• $b$ = How much the data is chopped up during each call.

• $O(k)$ = The extra work done *outside* the recursive calls (like printing a variable).

4. Scenario 1: Single-Branch Recursion (Linear) #

// O(n) Time Complexity
public void countToZero(int n) {
    if (n == 0) return; // Base Case
    System.out.println(n); // O(1) extra work
    countToZero(n - 1);    // T(n-1) recursive call
}

Analysis: It forms a straight line $N$ layers deep. Total Time is $O(n)$. Total Space is $O(n)$ (Stack Frames).

5. Scenario 2: Divide and Conquer (Logarithmic) #

// O(log n) Time Complexity
public int binarySearch(int[] arr, int left, int right, int target) {
    if (left > right) return -1;
    int mid = (left + right) / 2;
    if (arr[mid] == target) return mid; // O(1) work
    
    if (arr[mid] > target) 
        return binarySearch(arr, left, mid - 1, target); // T(n/2) call
    else 
        return binarySearch(arr, mid + 1, right, target); // T(n/2) call
}

Analysis: The matrix collapses logarithmically. Total Time is $O(\log n)$. Total Space is $O(\log n)$.

6. Scenario 3: Multiple Branches (Exponential) #

// O(2^n) Time Complexity
public int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2); // Two calls!
}

Analysis: The tree splits into 2, then 4, then 8... depth is $N$. Total Time is $O(2^n)$. (Space remains $O(n)$ because the OS only traverses one physical depth path at a time before returning!).

7. Scenario 4: Branching + Dividing (Linearithmic) #

8. Common Mistakes #

• Assuming Recursion is always $O(2^n)$: As proven above, recursion is just a tool. It can be $O(n)$ (straight line), $O(\log n)$ (Binary Search), $O(n \log n)$ (Merge Sort), or $O(2^n)$ (Fibonacci). You MUST physically draw the Execution Tree on paper to count the branches and depth!

9. Exercises #

1. 1. Analyze this Recurrence Relation: $T(n) = T(n/2) + O(n)$. What algorithmic concept does this represent, and what is its final simplified Big O notation?

1. 2. Why does a deep $O(2^n)$ Exponential recursive tree mathematically result in an $O(n)$ Linear Space Complexity instead of $O(2^n)$ Space?

10. MCQs with Answers #

12. Interview Preparation #

• *Mathematical Reductions:* "You write a recursive function traversing a matrix. The interviewer asks: You have a branching factor of 4, but you divide the data by 2. Is this faster or slower than $O(N^2)$?" *(Answer: Utilize the 'Master Theorem' of theoretical computer science! Because the branching weight ($4$) is greater than the data reduction weight ($2$), the calculation resolves to $O(N^{\log_2 4})$, which equals exactly $O(N^2)$! It is mathematically equivalent to a nested loop!)*

13. Summary #

14. Next Chapter Recommendation #