Informal Run-Time Analysis
Introduced| English |
|---|
| run time/rʌn taɪm/ |
| linear/ˈlɪnɪə/ |
| quadratic/kwɒˈdrætɪk/ |
Counting the work
- We measure a program's run time 运行时间 by how many times its key statements run.
- Not seconds (those vary by machine) — a count of operations as the input grows.
- More operations for the same input size → slower algorithm.
- This lets us compare algorithms fairly, independent of hardware.
A single loop: about n
- A loop over
nitems runs its body aboutntimes. - Double the input → about double the work. This is linear 线性 growth.
- Summing an array, searching a list one-by-one: all about
nsteps. - Written informally as "order
n."
A nested loop: about n²
- A nested loop over
nitems runs its inner body aboutn × n = n²times. - Double the input → about four times the work. This is quadratic 二次 growth.
- Comparing all pairs, filling an
n × ngrid: aboutn²steps. n²grows much faster thannasngets large.
Comparing growth
- To compare algorithms, ask how the work grows as the input grows.
- For large
n, annalgorithm beats ann²algorithm — often by a lot. - Focus on the part of the code that runs the most (usually the innermost loop).
- The fastest-growing term dominates the total run time.
Judge run time by GROWTH, not a fixed count. An algorithm that does n steps and one that does 2n + 5 steps both grow linearly — for comparing, the constant and the +5 don't matter; the shape (n vs n²) does. A single loop is about n; a nested loop is about n², which grows far faster for large inputs.
Two ways to find duplicates in n items:
- Nested loops comparing every pair: about
n²steps. - Sort first, then one pass: far fewer steps for large
n. - For
n = 1000,n²is a million steps — then²approach is much slower.
Informal run-time analysis counts how many times statements run as the input grows. A single loop over n items is about n (linear); a nested loop is about n² (quadratic), which grows much faster. Compare algorithms by their growth, focusing on the most-executed (innermost) code.
How the work grows with n
A nested loop (n²) grows far faster than a single loop (n).
A single loop over n items runs its body about how many times?
One loop over n items → about n steps (linear).
A nested loop over n items runs its inner body about how many times?
n × n = n² (quadratic).
For n = 1000, about how many steps is an n² algorithm (in millions)?
1000² = 1,000,000 = 1 million.
For large n, an n-step algorithm is generally faster than an n²-step one.
n² grows much faster, so it does far more work at large n.
We measure run time in seconds, which is the same on every computer.
We count operations vs. input size — seconds vary by machine.