Insight Vault

Input Size

4 min read

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.

The same raw input can have more than one meaningful size. A grid problem may use rows and cols. A problem about q queries over an array may use both n for the array length and q for the number of queries. A number-theory problem may depend on the numeric value, the number of digits, or both.

Choosing the input size is the first step in making a complexity statement precise.

Example Contract

contains_target(values, target) expects values to be an indexable or iterable collection and target to be the value being searched for.

It returns True when target appears at least once and False otherwise. The important input-size variable is n = len(values), because the function may need to inspect every value.

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.

If values has 10 items, the loop may run 10 times. If values has 1,000,000 items, the loop may run 1,000,000 times. The growth is controlled by the length of the list, not by the size of target.

How To Identify It

Ask what can grow in the problem statement.

  • If the input is a list, ask how many elements it has.
  • If the input is a string, ask how many characters it has.
  • If the input is a graph, ask how many vertices and edges it has.
  • If the input contains many queries, ask how many queries there are.
  • If the input is a number, ask whether the algorithm loops up to the number or only over its digits.

Then ask which of those growing quantities the algorithm actually touches.

A Small Trace

For this call:

contains_target([3, 8, 2, 9], 9)

the list length is 4. The loop checks 3, then 8, then 2, then 9. The input size for this analysis is n = 4, and the worst-case number of checks is proportional to n.

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.

Another common mistake is naming the size n without defining what n means. O(n) is not meaningful if the reader cannot tell whether n means array length, number of queries, number of vertices, or something else.

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.

A good complexity analysis begins by saying what the variables mean. For example: “Let n be the number of values and q be the number of queries.” After that, claims like O(n + q) become understandable.

The Main Point

Input size is the variable that explains how work grows. Before choosing an algorithm, identify what n actually counts and whether the expensive part is elements, pairs, states, edges, or output size.

Backlinks

Graph

Depth 1