Input Size

Input size is the amount of input an algorithm has to handle. It is the variable used to describe how the algorithm’s work grows.

The important question is not “how many bytes are in the file?” by default. The important question is which part of the input controls the number of steps the algorithm may take.

Core Idea

For an array problem, the input size is usually the number of elements, often called n. For a string problem, it is usually the number of characters. For a graph problem, there are often two input sizes: V for vertices and E for edges.

Input size must match the operation being analyzed. Searching a list of n numbers depends on n. Traversing a graph depends on both how many vertices exist and how many edges must be examined.

Python Example

def contains_target(values, target):
    for value in values:
        if value == target:
            return True
    return False

Here the input size is len(values). In the worst case, the function checks every element before returning.

Common Confusions

Input size is not always the numeric value of the input. If the input is the number 1_000_000, an algorithm may depend on the value itself, the number of digits, or both. The right choice depends on what the algorithm does.

Input size is also not always one variable. A graph with many vertices and few edges behaves differently from a graph with many vertices and many edges.

When To Use It

Use input size whenever comparing algorithms, estimating whether a solution will scale, or writing time and space complexity. Without a clear input size, a complexity claim such as O(n) has no precise meaning.