input size

The number, written n, that measures how big an input is, such as a list length, a row count or a string length.

In more detail

Complexity arguments describe work as a function of n, so the first step is always to say what n counts. For a graph there are often two sizes, V vertices and E edges, and costs are written with both. When n doubles, a linear algorithm does about twice the work while a constant-time one does the same work.

Related terms

Taught in

References