Measuring Running Time as a Function of Input Size

Imagine two programmers each hand you a sorting routine and both claim theirs is "fast." Without a shared way to measure speed, this claim is meaningless. Fast on what input, on what machine, compared to what? The first real step toward a science of algorithms is to stop asking "how many seconds does this take." Instead, we start asking "how does the work grow as the input grows." That question forces us to define a function, conventionally written $T(n)$ . This function reports the number of primitive operations an algorithm performs when given an input of size $n$ . This idea matters because real systems handle inputs whose size is never fixed. Input size is often unpredictable — a database query might touch ten rows or ten billion. A search engine indexes pages by the trillion. A compiler parses files ranging from a few lines to millions. An algorithm that is instantaneous on small inputs can be catastrophically slow on large ones. The only way to see this coming is to express running time as a function of input size, rather than as a single number. $T(n)$ is that function. Building it correctly is a foundational skill that everything else in algorithm analysis rests on. This means deciding what counts as "the input," what counts as "size," and what counts as an "operation." The big picture is this: running time is not a property of an algorithm in isolation. It is a relationship between an algorithm and a family of inputs, parameterized by size. Once we accept that framing, $T(n)$ becomes a precise mathematical object. It is built by counting how many times each primitive step in the RAM Model of Computation executes, then summing those counts. This is exactly the same activity as counting steps in a physics experiment or terms in a series. Nothing about it is approximate at this stage. The approximation, via asymptotic notation, comes later. This article delivers a careful, mechanical method for building $T(n)$ . This includes choosing $n$ , identifying primitive operations, and writing counting expressions for each line of pseudocode. It also involves summing them into a closed-form or bounded expression. It sets up, without yet introducing, the asymptotic simplifications (Big-O, Big- $\Omega$ , Big- $\Theta$ ). It also sets up the systematic loop-counting techniques that follow. These techniques follow directly from having a well-defined $T(n)$ in hand.

Key takeaways

Running time is measured as a function $T(n)$ of input size $n$ , not as a single number of seconds.
$n$ must be defined precisely for each problem (array length, number of vertices, bit-length of a number, etc.).
$T(n)$ is built by counting primitive operations from the RAM Model of Computation and summing their costs.
Different inputs of the same size can yield different operation counts — this is where best/worst/average case enters.
$T(n)$ is typically written as a sum of terms, each the product of a per-execution cost and an execution count.
This exact counting is the foundation for later simplification via Asymptotic Notation and systematic loop analysis.

The core insight

Running time becomes a rigorous, comparable quantity only once it is expressed as a function $T(n)$ of a precisely defined input size $n$ , built by summing counts of primitive operations.

The idea

An algorithm's running time is the total cost of the primitive operations it executes on a given input, where cost is measured in the RAM Model of Computation as a constant amount of time per operation (arithmetic, comparison, assignment, array indexing, and so on). But a single input gives a single number, and a single number tells us almost nothing about how the algorithm will behave on inputs we have not yet seen. The essential move in algorithm analysis is to treat running time not as a number but as a function of input size, denoted $T(n)$ , where $n$ is a natural number summarizing "how much input" the algorithm was given. Choosing $n$ is itself a modeling decision, not an automatic fact. For an array-processing algorithm, $n$ is usually the number of elements. For a graph algorithm, the natural choice is often a pair, the number of vertices $V$ and edges $E$ , or sometimes a single combined parameter. For an algorithm on integers — testing primality, for instance — the size should be the number of bits needed to represent the integer, not the integer's numeric value itself, because the RAM model charges cost per word or per bit, not per unit of magnitude. Getting this choice wrong (for example, treating the value $N$ as the size of an integer input instead of $\log N$ ) silently changes every subsequent complexity claim, so making $n$ explicit and defensible is the first task of any analysis. Once $n$ is fixed, $T(n)$ is constructed compositionally: each line or statement of an algorithm has some cost $c_i$ to execute once, and some number of times $t_i(n)$ it is actually executed as a function of $n$ (and possibly of the specific input, not just its size). The total running time is the sum

T(n) = \sum_i c_i \cdot t_i(n).

This single equation is the entire content of "measuring running time": identify the statements, cost each one, count how many times each runs, multiply, and add. Everything that comes later — Asymptotic Notation, the classification of loops, the notions of best-case/worst-case/average-case complexity — is built on top of this sum, either by bounding it, simplifying it, or taking it over different input distributions.

How it works

Building $T(n)$ for a piece of pseudocode is a mechanical, line-by-line process. The procedure below formalizes it.

Step 1 — Fix the input-size parameter. Decide what $n$ denotes for this problem: array length, number of nodes, number of bits, etc. State it explicitly.

Step 2 — Identify primitive operations. Under the RAM model, primitive operations include: arithmetic operations (+, −, ×, ÷), comparisons, assignments, array/field access, and control transfers (a loop test, a function call setup). Each is assumed to cost $O(1)$ actual time — some fixed constant, though the constant may differ operation to operation.

Step 3 — Annotate each line with a cost and an execution count. For each statement $i$ , write down $c_i$ (constant cost per execution — often left symbolic since its exact value depends on the machine/compiler) and $t_i(n)$ (number of times the line executes, which may depend on $n$ and, for inputs of the same size, on the specific input).

Step 4 — Sum. Add $c_i \cdot t_i(n)$ over all lines to obtain $T(n) = \sum_i c_i t_i(n)$ .

Step 5 — Simplify / bound. Collapse the sum into a closed form (using arithmetic series formulas for loops, for instance) and, if the count depends on more than the size (i.e., on the specific input), define worst-case, best-case, or average-case $T(n)$ by taking a max, min, or expectation over all inputs of that size. Here is the process carried out on a concrete algorithm — linear search for a target value in an array. ``` LINEAR-SEARCH(A, n, x) 1 for i = 1 to n 2 if A[i] == x 3 return i 4 return -1 ``` Line-by-line costs, letting $c_1, c_2, c_3, c_4$ denote the constant time for a loop-control step, a comparison, a return statement inside the loop, and the final return, respectively:

Line	Cost per execution	Number of executions
1 (loop control)	$c_1$	up to $n+1$ (the extra +1 for the final failing test)
2 (comparison)	$c_2$	up to $n$
3 (return on match)	$c_3$	$0$ or $1$
4 (return -1)	$c_4$	$0$ or $1$

If $x$ is not in the array (or is at the last position), lines 1 and 2 each execute the maximum number of times, and line 4 executes once, giving the worst-case running time

T(n) = c_1(n+1) + c_2 n + c_4 = (c_1 + c_2)\,n + (c_1 + c_4).

If $x$ is at position 1, lines 1 and 2 execute once each and line 3 executes once — the best-case running time

T(n) = c_1 + c_2 + c_3,

a constant, independent of $n$ . This single example already shows the key subtlety: $T(n)$ is not always a single well-defined function per size $n$ ; it can depend on which input of size $n$ is given, which is exactly why "worst case," "best case," and "average case" become necessary refinements once we start summing operation counts. ``` // General recipe for building T(n) from pseudocode FUNCTION BUILD-T(algorithm, n): total_cost := 0 for each line L in algorithm (in structural, not execution, order): c_L := constant unit-cost of executing L once // from RAM model t_L(n) := symbolic expression for how many times L executes, as a function of n (and possibly the specific input) total_cost := total_cost + c_L * t_L(n) return total_cost as T(n) ```

Figure

Building T(n): from pseudocode lines to a summed cost function

Complexity & correctness

"Correctness" here is not about the algorithm's output — it is about the analysis itself. The claim we must justify is: the sum $T(n) = \sum_i c_i t_i(n)$ correctly and exactly reports the total time the algorithm spends on an input of size $n$ , under the RAM model. The argument is a direct consequence of how the RAM model is defined. In that model, a program's execution is a finite sequence of primitive steps, each taking a fixed amount of time (allowed to differ between operation types, but not between instances of the same line). Total time is therefore, by definition, the sum over all executed instructions of their individual costs. Grouping this sum by line of source code rather than by individual instruction instance is valid because instances of the same line all cost the same $c_i$ — so

\text{total time} = \sum_{\text{instructions executed}} \text{cost} = \sum_{\text{lines } i} c_i \times (\text{number of times line } i \text{ executes}) = \sum_i c_i\, t_i(n).

This is not an approximation; it is exact bookkeeping, as long as $t_i(n)$ is computed correctly for the given input. The only subtlety is that $t_i$ may depend on more than $n$ — two inputs of the same size can force different execution counts (as in linear search, where a "hit" at position 1 and a "miss" produce wildly different line-3 and line-4 counts). This is precisely why $T(n)$ alone is sometimes ambiguous, and the standard resolution is to define three distinct functions:

Worst-case $T(n) = \max$ over all inputs of size $n$ of the actual running time — a guarantee that no input of that size does worse.
Best-case $T(n) = \min$ over all inputs of size $n$ — often less useful as a guarantee, but useful for lower-bound intuition.
Average-case $T(n) = \mathbb{E}[\text{running time}]$ under some assumed distribution over inputs of size $n$ — powerful but only as meaningful as the distributional assumption.

Complexity of computing $T(n)$ itself. This is a meta-question worth being honest about: constructing $T(n)$ for a piece of code with loop nesting depth $d$ and no data-dependent branching typically requires evaluating nested summations, which for straightforward polynomial loop bounds resolve in closed form using standard series identities (arithmetic series $\sum_{i=1}^n i = n(n+1)/2$ , geometric series, etc.) — an operation that is itself "fast" (it is symbolic algebra, not something we run at execution time). The genuine difficulty is not computing the sum once counts are known; it is correctly determining $t_i(n)$ for data-dependent control flow, which is where case analysis (best/worst/average) becomes unavoidable.

Tradeoffs to be honest about. Exact $T(n)$ , expressed with explicit constants $c_i$ , is precise but fragile: the constants depend on the compiler, the instruction set, cache behavior, and other machine details not modeled at this level of abstraction. This fragility is exactly the motivation for moving to Asymptotic Notation, which discards the constants and lower-order terms and keeps only the growth rate — but that step is only trustworthy because it is built on top of an honestly and completely constructed $T(n)$ . Skipping straight to "it's obviously $O(n^2)$ " without ever writing the sum is how subtle errors (miscounting a loop bound, forgetting an operation, conflating value and bit-length as the size parameter) slip through unnoticed.

Worked example

Consider insertion sort, a slightly richer example where the execution count of the inner loop genuinely depends on the specific input, not just on $n$ . ``` INSERTION-SORT(A, n) 1 for j = 2 to n 2 key = A[j] 3 i = j - 1 4 while i > 0 and A[i] > key 5 A[i+1] = A[i] 6 i = i - 1 7 A[i+1] = key ``` Let $t_j$ denote the number of times the `while`-test in line 4 is evaluated during the $j$ -th outer iteration (this is the input-dependent quantity). Costs $c_1,\dots,c_7$ are the constant per-execution costs of each line.

Line	Cost	Executions
1	$c_1$	$n$ (the loop runs for $j=2,\dots,n$ , plus the final failing test)
2	$c_2$	$n-1$
3	$c_3$	$n-1$
4	$c_4$	$\sum_{j=2}^{n} t_j$
5	$c_5$	$\sum_{j=2}^{n} (t_j - 1)$
6	$c_6$	$\sum_{j=2}^{n} (t_j - 1)$
7	$c_7$	$n-1$

Summing gives the general form

T(n) = c_1 n + (c_2+c_3+c_7)(n-1) + c_4 \sum_{j=2}^n t_j + (c_5+c_6)\sum_{j=2}^n (t_j - 1).

Now trace two concrete inputs of the same size $n = 5$ to see $t_j$ diverge:

Input A — already sorted: $A = [2, 5, 7, 9, 12]$ . For each $j$ , `A[i] > key` is false immediately (the element to the left is never larger), so $t_j = 1$ for every $j = 2,\dots,5$ .

\sum_{j=2}^5 t_j = 4, \qquad \sum_{j=2}^5 (t_j - 1) = 0.

T(5) = c_1(5) + (c_2+c_3+c_7)(4) + c_4(4) + (c_5+c_6)(0),

a best-case running time — linear in $n$ for this family of inputs.

Input B — reverse sorted: $A = [12, 9, 7, 5, 2]$ . Now every new key must shift past all previously placed elements: $t_j = j$ for $j=2,\dots,5$ (the while-loop runs until `i` hits 0, i.e., $j-1$ comparisons succeed plus one failing test, giving $t_j = j$ ).

\sum_{j=2}^5 t_j = 2+3+4+5 = 14, \qquad \sum_{j=2}^5 (t_j-1) = 1+2+3+4 = 10.

T(5) = c_1(5) + (c_2+c_3+c_7)(4) + c_4(14) + (c_5+c_6)(10),

a worst-case running time — quadratic in $n$ in general, since for reverse-sorted input of general size $n$ ,

\sum_{j=2}^n j = \frac{n(n+1)}{2} - 1,

a term proportional to $n^2$ . Same algorithm, same $n=5$ , wildly different $T(n)$ — precisely because $t_j$ depends on the specific arrangement of the input, not merely on its size. This is the concrete phenomenon that forces best-/worst-/average-case running time to be defined as separate functions rather than a single $T(n)$ .

Common pitfalls & traps

Pitfall	Why it happens	Consequence
Using the numeric value of an input as $n$ instead of its size in bits	Confusing "the number" with "the encoding of the number"	Algorithms on integers (e.g., primality testing) look exponential when they are actually polynomial in the true input size
Forgetting the "extra" loop-test execution	A `for`/`while` loop tests its condition one more time than the body executes	Off-by-one error in $t_i(n)$ , e.g. writing $n$ instead of $n+1$
Treating $T(n)$ as if it were single-valued per $n$	Ignoring that execution counts can be input-dependent, not just size-dependent	Silently reports "the" running time when only best/worst/average case is meaningful
Counting only the outer loop, ignoring nested-loop dependence	Sloppy line-by-line accounting; treating nested loops as if independent of the outer index	Miscounts total operations (e.g., missing that insertion sort's inner loop bound depends on $j$ )
Assuming all primitive operations cost the same constant	RAM model gives O(1) cost per operation, but the constants genuinely differ (e.g., multiply vs. increment)	Overprecise/misleading comparisons between algorithms based on raw constant counts

Pioneers & history

The idea of measuring computational cost as a function that grows with problem size emerges from the convergence of several lines of thought: formal models of computation, the early practice of algorithm design, and the mathematics of asymptotic growth borrowed from analysis and number theory.

Origins · 1 minAlan Turing and how this was discovered

Alan Turing

1912–1954 · Formalized the notion of mechanical computation via the Turing machine, providing the substrate on which "steps taken as a function of input" could later be made rigorous

Donald E. Knuth

1938–present · Systematized the analysis of algorithms in The Art of Computer Programming, popularizing precise operation-counting and the running-time function

T(n)

as the standard object of study

History

1936

— Turing formalizes mechanical computation, giving a rigorous notion of "step" for later cost-counting.

1949

— early computer designers begin informally estimating instruction counts for numerical routines.

1965

— Jack Edmonds argues informally for "efficient" algorithms as those with polynomially bounded step counts in input size.

1968

— Knuth's The Art of Computer Programming Volume 1 formalizes counting primitive operations as

T(n)

1971

— Cook's theorem on NP-completeness cements input-size-parameterized running time as the field's central quantity.

Where this matters

Every performance-sensitive system implicitly reasons in terms of $T(n)$ . Database query planners estimate cost as a function of table size before choosing a join strategy. Compilers reason about the size of an abstract syntax tree when deciding how aggressively to optimize a pass. Network routers must bound per-packet processing time as a function of routing-table size to guarantee throughput under load. Cryptographic protocols are designed and broken based on whether an attack's running time is polynomial or exponential in the bit-length of the key — exactly the input-size subtlety highlighted above. Machine learning pipelines profile training time as a function of dataset size and feature dimension before scaling to production data. In every one of these settings, the discipline of first fixing $n$ , then constructing $T(n)$ by counting operations, is what turns "this seems slow" into a claim that can be checked, compared, and trusted — and it is the necessary foundation before growth rates are compared abstractly via Asymptotic Notation or loop structures are analyzed systematically as in Analyzing Loops by Counting Operations.

Ask the tutor: Can you walk through building T(n) for a doubly-nested loop where the inner bound depends on the outer index?

Why isn't "running time in seconds" a good enough measure on its own?

Running time in seconds mixes together the algorithm's inherent workload with machine-specific facts: clock speed, compiler optimizations, cache behavior, and even background system load. Two runs of the identical algorithm on different hardware, or even the same hardware under different conditions, can report different wall-clock times without the algorithm having changed at all. Measuring running time as a function $T(n)$ of input size instead separates the algorithm's behavior — how the number of primitive operations grows — from these incidental machine effects. The constants $c_i$ absorb machine-dependence, while the shape of $T(n)$ as $n$ grows captures something intrinsic to the algorithm, which is exactly what later gets distilled further via Asymptotic Notation.

Is T(n) always a polynomial or simple closed-form expression?

Not necessarily. $T(n)$ is defined as a sum of costs times execution counts, and for straightforward loop-based algorithms this sum often does resolve into a closed form using standard series identities. But for algorithms with recursive structure, $T(n)$ is more naturally expressed as a recurrence relation (e.g., $T(n) = 2T(n/2) + cn$ for merge sort) rather than a closed form directly. Solving such recurrences (by substitution, recursion trees, or the Master Theorem) is a distinct — though related — skill built on top of correctly setting up $T(n)$ in the first place.

How does choosing n incorrectly break an entire analysis?

Every subsequent step — the operation counts $t_i(n)$ , the sum $T(n)$ , and any later asymptotic classification — is defined relative to $n$ . If $n$ does not faithfully represent "how much input the algorithm actually receives," the resulting function describes growth with respect to the wrong quantity. The classic failure mode is treating the value of a numeric input as its size instead of its bit-length; this single choice can make an algorithm appear to have exponential running time in the "size" you chose when it is actually polynomial in the true (bit-length) size, or vice versa. There is no way to recover from this downstream — the fix must happen at the point $n$ is defined.

What's the difference between T(n) for a specific input and T(n) as worst-case complexity?

$T(n)$ , in the fullest sense, is a value that can depend on the specific input, not merely on its size $n$ — two arrays of the same length can force an algorithm through different execution paths. "Worst-case complexity" is a derived, single-valued function of $n$ obtained by taking the maximum of $T(n)$ over all inputs of that size. It is a guarantee: no input of size $n$ will exceed it. Best-case and average-case are the analogous minimum and expectation. All three are built from the same underlying per-input $T(n)$ ; they differ only in how they aggregate over the inputs of a fixed size.

Does building T(n) by hand scale to large, complex programs?

For small procedures with simple control flow, hand-counting each line is entirely feasible and is exactly the discipline this article develops. For larger programs, the same principle applies but the bookkeeping is organized around structural rules: sequential statements add their costs, loops multiply a body's cost by an iteration count (possibly itself needing analysis, as with nested loops), and conditionals take the cost of whichever branch actually executes (or the worst of the branches, for worst-case analysis). This structural, compositional view — formalized further in Analyzing Loops by Counting Operations — is what allows the technique to scale beyond toy examples without abandoning the underlying "sum of cost times count" definition.

Why do we eventually discard the constants c_i if they're part of an honest T(n)?

The constants $c_i$ are genuinely part of the true running time, but they depend on details — machine architecture, compiler, instruction encoding — that are outside the scope of what an algorithm's design controls. Once $T(n)$ has been honestly constructed as $\sum_i c_i t_i(n)$ , Asymptotic Notation provides a principled way to discard the $c_i$ 's and lower-order terms, keeping only the dominant growth rate as $n \to \infty$ . This is not a shortcut around doing the counting — it is a simplification applied after the counting has been done correctly, which is why this article's exact-sum construction is a prerequisite rather than an alternative to asymptotic analysis.