Skip to content
Tutorials Center
My learning

Topics

C++ Reference ยท Algorithms

C++ algorithm complexity guarantees

What the C++ standard guarantees about the cost of algorithms: comparisons, swaps, iterator requirements, amortized time, and a cheat sheet from find to sort.

The C++ standard does not just say what each standard algorithm does; it also says how much work it may do. These complexity guarantees are part of the contract. They are stated as a number of specific operations (comparisons, applications of a predicate, swaps, assignments) in terms of N, the length of the range, and not as seconds. That is why you can reason about performance before you write any benchmark, and why a conforming library cannot quietly replace an O(n log n) sort with an O(nยฒ) one.

The guarantees also depend on the iterator category. std::lower_bound does O(log n) comparisons on any forward iterator, but it only makes O(log n) iterator steps on random-access iterators; on a std::list it still walks O(n) nodes. Reading a complexity guarantee therefore means reading two things: what is counted, and what the iterators cost.

C++
std::find(v.begin(), v.end(), x);          // at most N comparisons
std::sort(v.begin(), v.end());             // O(N log N) comparisons, worst case (C++11)
std::lower_bound(v.begin(), v.end(), x);   // O(log N) comparisons, v must be sorted

Try it

C++ Counting what the standard counts

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

C++ Why the data structure matters: the same call, different cost

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

Syntax

There is no syntax: the guarantee is written in the description of each algorithm. These are the common phrasings.

Phrase in the standard Meaning
"Exactly N applications" Always N calls of the predicate or function. for_each, transform, count.
"At most N applications" Stops early when possible. find, all_of, any_of.
"At most N log N comparisons" sort, stable_sort has "N log N, or N logยฒ N without extra memory".
"O(log N) comparisons" lower_bound, upper_bound, binary_search, equal_range, push_heap, pop_heap.
"Linear" or "at most N-1" adjacent_find, unique, is_sorted, merge, min_element, make_heap (3N).
"Amortized constant" Cost averaged over many calls; vector::push_back.

Returns: not applicable.

Errors / undefined behavior: a predicate or comparator that is not consistent can break the complexity guarantee as well as the result, and with some algorithms causes undefined behavior (see Writing comparators).

Usage notes

  • Cheat sheet. find, count, copy, fill, reverse, rotate, remove, unique, accumulate: O(n). sort, stable_sort, partial_sort (O(n log k)): O(n log n). nth_element: O(n) on average. binary_search family: O(log n) comparisons. merge and set operations: O(n + m). Heap functions: make_heap O(n), push_heap and pop_heap O(log n), sort_heap O(n log n).
  • std::sort is O(n log n) in the worst case since C++11. Before that implementations could be quadratic on adversarial input. stable_sort uses extra memory when available to reach O(n log n); without it, O(n logยฒ n).
  • Iterator category changes the real cost. std::distance and std::advance are O(1) for random-access iterators but O(n) otherwise. A "logarithmic" lower_bound on std::list still performs O(n) iterator increments. Prefer std::set::lower_bound or sorted vectors for lookups.
  • Containers have their own guarantees: vector::insert in the middle is O(n), list::splice is O(1), unordered_map::find is O(1) on average and O(n) worst case. See Container complexity.
  • Hidden costs. The guarantee counts operations of the element type. Sorting a vector<std::string> makes O(n log n) string comparisons, each of which can cost O(length). Sorting large objects moves a lot of data; sorting indices or pointers can be faster.
  • Expected versus worst case. nth_element and unordered_map are average-case linear/constant. Do not use them where an attacker can choose the input without considering the worst case.
  • Stable and in-place do not always go together. stable_sort and inplace_merge allocate memory for speed and may throw std::bad_alloc on failure, falling back to slower code when allocation fails.
  • Measure. Big-O hides constants and caches: for small n a linear scan of a vector often beats std::set. Count with a lambda as the first example does, or benchmark.
  • Parallel algorithms keep the same operation counts as upper bounds (with some slack) but divide the work between threads. See Execution policies.