Think together · Start with a little story
Finding one card among ten feels quick. With a million cards, the difference between search methods becomes obvious.
Lay out the process
- Search in orderYou might check a million cards
- Halve an ordered setRemove about half each time
- CompareCount key operations, not lines of code
Program running time depends on the algorithm, input size, implementation, and hardware.
Counting the key repeated operation helps show how the work grows as the input gets larger. Even short code can do a huge amount of work.
01Why can programs run at very different speeds on the same computer?
Because they do different amounts of work.
For example, when looking for a number:
- Linear search may examine many elements.
- Binary search rules out half the remaining elements each time.
02Can a faster computer solve every problem?
No.
If an algorithm’s work grows like n² or 2n instead of n, the work can grow much faster than hardware gets faster as the input grows.
03A simple comparison
| n | n | n² | 2n |
|---|---|---|---|
| 10 | 10 | 100 | 1,024 |
| 20 | 20 | 400 | 1,048,576 |
| 30 | 30 | 900 | About 1.07 billion |
04Does each line of code count as one operation?
No. Complexity analysis does not mechanically count source-code lines.
We care more about how the number of key operations grows with the input size.
05What else affects actual running time?
Hardware
CPU, memory, and cache.
Compiler optimizations
A compiler may optimize the code.
Input data
Different inputs may take different paths.
I/O
A lot of reading and writing can become a bottleneck.
06Why learn complexity?
Complexity helps us set aside machine details and first ask:
What have you learned?
- Program speed is closely related to the amount of work the algorithm does.
- Faster hardware cannot make up for every poor algorithm.
- Complexity focuses on how work grows with the input size.
- The number of source-code lines is not the number of algorithmic operations.
- Actual running time also depends on hardware, I/O, optimizations, and other factors.
Next: What Is Time Complexity?
Your turn to try
If a one-line loop repeats a billion times, will its short code make it fast?
Ready? Open to see the explanation
No. Code length is not the number of executions. Look at how many times the loop repeats and what it does each time.