More Example Recurrences

The Recursion Tree Method is a visual way to analyze the time complexity of recursive algorithms. Let's break down three key examples using recursion trees and calculate their time complexities.

Example 1: Exponential Recursion

Recurrence Relation: $T(n) = 2T(n-1) + C$ and $T(1) = C$

Recursion Tree:

Level 0: $C$
Level 1: $T(n-1), T(n-1) \implies 2C$
Level 2: $T(n-2), T(n-2), T(n-2), T(n-2) \implies 4C$
...
Level $k$: $2^k C$

Analysis:

Cost at Each Level:
- Level 0: $C$
- Level 1: $2C$
- Level 2: $4C$
- ...
- Level $n$: $2^{n-1} C$
Total Levels: The tree has $n$ levels (since the problem size reduces by 1 at each level).
Total Cost: $C + 2C + 4C + ... + 2^{n-1}C = C(2^n - 1)$.
Time Complexity: $\Theta(2^n)$.

Example 2: Single Recursive Call

Recurrence Relation: $T(n) = T(n/2) + C$ and $T(1) = C$

Recursion Tree:

Level 0: $C$
Level 1: $C$
Level 2: $C$
...
Level $k$: $C$

Analysis:

Cost at Each Level: Each level contributes $C$.
Total Levels: The tree has $\log_2 n$ levels (since the problem size halves at each level).
Total Cost: $C \times \log_2 n$.
Time Complexity: $\Theta(\log n)$.

Example 3: Two Recursive Calls

Recurrence Relation: $T(n) = 2T(n/2) + C$ and $T(1) = C$

Recursion Tree:

Level 0: $C$
Level 1: $2 \times C = 2C$
Level 2: $4 \times C = 4C$
...
Level $k$: $2^k C$

Analysis:

Cost at Each Level:
- Level 0: $C$
- Level 1: $2C$
- Level 2: $4C$
- ...
- Level $k$: $2^k C$
Total Levels: The tree has $\log_2 n$ levels.
Total Cost: $C + 2C + 4C + ... + 2^{\log_2 n} C = C(2 \cdot 2^{\log_2 n} - 1) = C(2n - 1)$.
Time Complexity: $\Theta(n)$.

Conclusion

By using the Recursion Tree Method, we can visually analyze recursive algorithms and determine their time complexities. In the examples above:

Exponential Recursion: $\Theta(2^n)$
Single Recursive Call: $\Theta(\log n)$
Two Recursive Calls: $\Theta(n)$

This method is a powerful tool for understanding and optimizing recursive algorithms.

Recursion Tree Method Time Complexity