input size

Input size is how big the job is, measured by a single number we call n. Sorting ten names is a small job; sorting ten million is a big one. To talk about how an algorithm's running time grows, we first need a fair yardstick for "how big" each input is — and that yardstick is the input size. For a list, n is usually the number of items; for a piece of text, n is the number of characters; for a graph, we often use two numbers, the count of vertices and the count of edges.

More carefully, input size means the amount of data needed to describe the instance, often counted in the number of items or, more strictly, the number of bits to write it down. The strict version matters for numbers: the integer 1000000 has value one million but takes only about 20 bits to write, so its "size" as input is about 20, not a million. This is why an algorithm whose running time depends on the value of a number, rather than on the number of bits, can secretly be exponential in the input size. We express cost as a function of n — say, about n comparisons, or about n^2, or about n log n — so that we can ask the real question: as n doubles, what happens to the work?

Choosing the right size measure is a modelling decision, and a sloppy choice can mislead. For multiplying two n-digit numbers, the size is the number of digits, not the size of the numbers themselves. For a graph algorithm, reporting a bound "in terms of n" is ambiguous until you say whether n counts vertices, edges, or both. Pinning down the size measure first is what lets every later statement about speed and growth actually mean something.