Operation Counting Pros and Cons
Like any theoretical analysis, operation counting has both strengths and limitations.
It's very useful for answering some kinds of questions, less so for others.
Role of Operation Counting
Operation counting abstracts away the compiler and system details entirely.
- Yay: This is about an algorithm not a program. It's meaningful even without system-level details.
- Yay: If we count the most expensive operations, we can use the counts to compare different algorithms.
- Boo: There's no guarantee that the number of operations is an indication of runtime of an actual program.
- Boo: We have to make choices about what operations to count and it may not always be obvious.
Operation counting gives us a specific expression to represent the exact (or approximate) count.
- Yay: Specifics matter. Doing an expensive operation 10 times more or less often can make a big practical difference!
- Boo: Sometimes specifics are distracting. Sometimes we want to focus on big, qualitative differences.
- Boo: Our expression depends on our choice of what precisely we're counting with \( n \). Different choices might give us more or less useful results, or more often, similar but not identical formulas (e.g., \( 3n + 1 \) vs. \( 4n - 2 \)).
- Boo: Sometimes getting an exact count is more effort than we need to put in for the questions we want to answer.
Our list suggests that we might benefit from moving up another layer of abstraction.
-
Next we'll consider a type of analysis that leaves out even more detail and focuses on big differences between algorithms.
(When logged in, completion status appears here.)