Asymptotic Notation

This chapter introduces Big-Oh notation, a way to measure how much work an algorithm does that does not depend on the machine it runs on. It covers the two rules that turn a step count into a Big-Oh, how to read a Big-Oh directly from code, and how to use it to compare DynamicArray and SortedArray and choose between them for a workload.

After reading this chapter, you should be able to:

• Explain why timing a run or counting one chosen operation both fail to measure how an algorithm scales, and why we want a measure of work that ignores the machine, language, and coding style
• Translate a cost expression such as $\alpha n^2+\beta n+\gamma$ into Big-Oh by suppressing coefficients and dropping lower-order terms, and justify why both simplifications are valid
• Read an algorithm’s Big-Oh directly from its code by locating the dominant work, including work built from calls into other operations: sequential loops add, nested loops multiply, a triangular loop is still $O(n^2)$, and a loop counter that multiplies or divides by a constant each iteration is $O(\log n)$
• Reason about DynamicArray and SortedArray operation costs from what each structure must do, and choose between them for a workload by weighing search frequency against update frequency, and explain why sorting on demand does not avoid that trade-off
• Interpret a Big-Oh class as a family of functions sharing a growth rate, order the common families from $O(1)$ through $O(n!)$, and determine which of two algorithms is faster for large $n$

Sections

1. Why We Need a Way to Analyze Algorithms
2. Why Not Just Time Them?
3. Big-Oh Notation
4. Why We Suppress Coefficients
5. Why We Drop Lower Terms
6. Reading Big-Oh from Code
7. Two Loops, Still Linear
8. Nested Loops Multiply
9. Half the Work, Same Class
10. A Loop That Doubles
11. Building Up to Selection Sort
12. Reasoning About Operations Without the Code
13. Which Structure for the Roster?
14. Why Not Sort Only When We Search?
15. Growth Rate
16. Common Running Times