What does time complexity mean?

AlgorithmsJunior~4 min read

Short answer

Time complexity is an estimate of how an algorithm's running time changes as the size of the input data n grows. It is most often expressed asymptotically using Big-O notation, ignoring constants and lower-order terms. Example: binary search runs in O(log n), two nested loops over an array run in O(n²).

Detailed breakdown

What time complexity is

It is a way to describe how fast the number of an algorithm's elementary operations grows depending on the input size n. We do not measure milliseconds, but count basic steps (comparisons, assignments, accesses to data structures) and look at how their number grows as n increases.

It measures not the exact time, but the order of growth of operations.
We count elementary operations; the specific "time on a machine" is abstracted away.
We look at n and ignore constant factors and lower-order terms.

Notations: O, Θ, Ω

O(f(n)) - an upper bound (no slower than f(n), up to a constant). Often used for the "worst case".
Θ(f(n)) - a tight asymptotic bound (both the upper and lower bounds match in order).
Ω(f(n)) - a lower bound (no faster than f(n), up to a constant).

Cases of estimation

Worst case: a guaranteed upper bound.
Average case: the mathematical expectation over the distribution of inputs.
Best case: the most favorable combination of circumstances.

How to estimate complexity (rules)

Sequential fragments are added together. Take the dominant term (of the higher order).
A single loop over n is O(n), if the loop body is O(1).
Nested loops are multiplied (for example, two loops over n give O(n²)).
Halving the problem at every step gives O(log n) (binary search).
"Divide and conquer": T(n) = a·T(n/b) + f(n). Often gives O(n log n) (for example, merge sort).
Typical data structure operations:

Hash table: search/insert/delete - expected O(1), worst case O(n).
Heap (priority queue): insert/extract - O(log n).
Balanced search tree: search/insert/delete - O(log n).

Typical complexities and examples

Notation	Example	Comment
O(1)	Indexed access, amortized push on a dynamic array	Does not depend on n
O(log n)	Binary search, operations on a balanced BST	Each step reduces the search by a constant factor
O(n)	A linear pass over an array	Proportional to the input size
O(n log n)	Merge sort, heap sort, quicksort (on average), building a heap	Common in "divide and conquer"
O(n²)	Two nested loops, bubble sort	Quadratic growth of operations
O(2^n)	Enumerating all subsets	Exponential growth, quickly becomes impractical
O(n!)	Enumerating all permutations (for example, brute-force TSP)	Factorial growth, does not scale in practice

Code examples

Binary search - O(log n)

function binarySearch(arr, x) {
  let l = 0, r = arr.length - 1;
  while (l <= r) {
    const m = l + ((r - l) >> 1);
    if (arr[m] === x) return m;
    if (arr[m] < x) l = m + 1; else r = m - 1;
  }
  return -1; // not found
}
// The number of loop iterations ≈ log2(n)

Two nested loops - O(n²)

function countPairsEqual(arr) {
  let count = 0;
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] === arr[j]) count++;
    }
  }
  return count; // quadratic complexity
}

Finding a pair with a given sum in O(n) time and O(n) memory

function hasPairWithSum(arr, target) {
  const seen = new Set();
  for (const v of arr) {
    if (seen.has(target - v)) return true;
    seen.add(v);
  }
  return false;
}
// A linear pass plus a hash table: expected O(1) per operation, O(n) overall

Amortized complexity (briefly)

Sometimes an individual operation can take a lot of time, but the average cost over a series of operations is constant. The classic example is push on a dynamic array that doubles its capacity.

Most pushes are O(1): we simply write the element into a free slot.
Occasionally a resize and copy happens - O(n) for that step.
If the size is doubled, the total cost of N insertions is O(N), so it is amortized O(1) per insertion.

Practical remarks

Constants and caches matter in practice: two algorithms with the same O-estimate can behave very differently.
The distribution of the input data affects the average case.
Pre-sorting often changes the complexity of subsequent steps.
Hash table operation estimates are expected values; in the worst case they are O(n) due to collisions.
Remember space complexity and the time-memory trade-offs.

Interview checklist

Define what n is (array length, number of vertices, number of edges, and so on).
State the worst and average case, if relevant.
Work through loops and recursion: sum/multiply correctly.
Reduce to the dominant term and simplify to Big O.
Note additional resources: memory, I/O, network calls.

Brief summary

Time complexity shows the order of growth of an algorithm's running time as the input grows. Use Big O for the upper bound, consider the scenarios (best/average/worst), know the typical complexities, and be able to quickly estimate them from the structure of loops and recursion.

Short Answer

Interview ready

Premium

A concise answer to help you respond confidently on this topic during an interview.