Complexity Analysis

This chapter covers the fundamentals of complexity analysis. A complexity claim about an algorithm has to say which case it assumes (best, worst, or average), which resource it measures (time or space), and whether it covers one operation or a sequence (amortized cost). Along the way, we cover a few other related topics. For example, we work out how much memory recursion uses on the call stack, and why a dynamic array doubles its capacity when it grows.

After reading this chapter, you should be able to:

• Determine an algorithm’s best-, worst-, and average-case time complexity, and apply the convention that an unqualified Big-Oh names the worst case
• Determine an algorithm’s space complexity, separating the input space from the auxiliary space it allocates while running
• Determine a recursive method’s space from its maximum call-stack depth, and explain why its time and space can differ, as they do for recursive Fibonacci
• Define the amortized cost of a sequence of operations, distinguish it from average-case cost, and explain why doubling the capacity makes a dynamic array’s add $O(1)$ amortized
• State a complete complexity claim, naming which resource it measures, which case it assumes, and whether it covers a single operation or a sequence

You can download the accompanying code for this chapter.

Sections

1. Time Complexity
2. Best Case and Worst Case
3. Average Case Analysis
4. Space Complexity
5. Space Complexity of Recursion
6. Time and Space of Recursive Fibonacci
7. A Faster Fibonacci
8. A Leaner Fibonacci
9. Complexity of grow and add
10. Amortized Analysis
11. Growing One Slot at a Time
12. Why Doubling Works
13. Computational Complexity