NZ NCEA Level 3 Digital Technologies

## Why running time is not the measure Timing a program with a stopwatch says as much about the computer as about the algorithm. A slow algorithm on a fast machine can beat a fast algorithm on a slow one, and the result changes with the language, the compiler, what else is running and the particular input. Computer scientists therefore measure an algorithm by how the amount of work it does grows as the input grows. The input size is written $n$: the number of items in a list, the number of cities in a route, the number of digits in a number. Work is counted in basic steps, such as a comparison, an assignment or an arithmetic operation, each treated as taking one unit of time. The count is a function of $n$, and what matters is the shape of that function for large $n$. This is **time complexity**. **Space complexity** is the same idea applied to memory: how much extra storage the algorithm needs as $n$ grows, not counting the input itself. ## Counting steps Consider a function that finds the largest value in a list of $n$ numbers. ```python def largest(items): best = items[0] for x in items[1:]: if x > best: best = x return best ``` The loop runs $n - 1$ times and each pass does one comparison and possibly one assignment. The total is roughly $2n$ steps at most, plus a constant for the set-up. Doubling the list doubles the work. Whether the exact figure is $2n$ or $3n + 5$ does not change that, which is why the constants are dropped. Now a function that checks whether any…