Time complexity

Fundamentals

At a glance

Time complexity describes how the amount of work changes when the input gets larger. It is not the exact number of seconds an algorithm takes. If doubling the input approximately doubles the number of loop iterations, a linear model such as O(n) is often appropriate.

What counts as an operation?

You choose an operation that reasonably reflects the work, such as reading an array element or performing a comparison. Constant-time operations are treated as having roughly constant cost in the model. Hardware, memory caches, and language runtimes can still affect actual speed.

Work through three examples

Constant

int first = values[0]; // O(1), if the array is nonempty

int first = values.at(0); // O(1), throws if empty

The number of accessed items stays the same when the array grows.

Linear

foreach (int value in values)
    Console.WriteLine(value); // O(n) total

for (int value : values)
    std::cout << value << '\n'; // O(n) total

The loop visits each of the n elements once.

Quadratic

for (int i = 0; i < values.Length; i++)
    for (int j = 0; j < values.Length; j++)
        Compare(values[i], values[j]); // O(n²) total

for (std::size_t i = 0; i < values.size(); ++i)
    for (std::size_t j = 0; j < values.size(); ++j)
        compare(values[i], values[j]); // O(n^2)

There are n × n calls when both loops cover the whole input.

How to estimate complexity from code

Define n. Identify exactly what grows, such as the number of items in an array.
Choose a representative operation. Counting comparisons or assignments is often more informative than counting source lines.
Count repetition. A single loop over n elements is usually linear. A loop whose range halves each iteration is usually logarithmic.
Combine parts. Consecutive sections have added costs; nested loops often multiply their iteration counts.
Keep the dominant term. 3n² + 2n + 8 is O(n²) as an upper bound. Mention assumptions such as early exits.

Best, average, and worst case

Linear search has a best case of one comparison when the target is first. Its worst case examines the entire list. A uniformly random target position gives an average proportional to n, assuming the target is present and positions are equally likely.

When theory meets real code

O(n log n) does not automatically beat O(n²) for every small input. Constants, allocations, branch prediction, and cache locality can outweigh growth rate at small sizes. Complexity helps predict scaling; measurement helps choose between real implementations.

Multiple loops are not always quadratic

Two loops one after another, each visiting n items, take n + n iterations and are still linear. A loop nested inside another loop is often quadratic, but only when both visit approximately n items each. A triangular loop (j < i) performs about n(n-1)/2 iterations and is still Θ(n²).

Hidden work in helper methods

A single line such as collection.Contains(value) is not guaranteed to be constant time. The cost depends on the collection type and its implementation. A linear search through a list and a typical hash-based membership test have different average behavior. Read the API contract when analyzing code, not just the surrounding loops.

Choosing a useful test

Measure multiple input sizes and keep the environment consistent. Record the exact dataset and whether the input is random, sorted, or adversarial. One fast run on tiny input says little about asymptotic growth.