[Python] Understanding Time Complexity and Space Complexity in Recursive Algorithms

I am trying to analyze and optimize recursive algorithms, particularly with regards to their time and space complexity. I have written a recursive solution for the Fibonacci sequence and a merge sort implementation, but I'm struggling to understand how to properly calculate their Big O complexity.

Specifically:

1. How do I determine the recurrence relation for recursive algorithms?

2. Why does the naive Fibonacci approach have O(2^n) time complexity while memoization reduces it to O(n)?

3. How should I account for the call stack depth when calculating space complexity?

4. Are there any tools or techniques to verify my complexity analysis empirically?

I would appreciate examples with detailed explanations of how the recursion tree expands and how that translates to complexity notation.

Continue reading...