Introduction

std::next_permutation has worst-case linear cost for a single call, but its amortized cost over a full sweep of permutations is constant. The reason is that the long suffix reversals people worry about happen rarely, while short suffix updates happen most of the time.

How std::next_permutation Works

The algorithm does three main things:

1. Scan from the right to find the first position where the sequence stops descending.
2. Swap that pivot with the smallest larger value to its right.
3. Reverse the suffix after the pivot.

Here is a small example:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6    std::vector<int> values{1, 2, 3};
7
8    do {
9        for (int x : values) {
10            std::cout << x << ' ';
11        }
12        std::cout << '\n';
13    } while (std::next_permutation(values.begin(), values.end()));
14}

Each call moves to the next lexicographic arrangement, or resets to the first one and returns false if the current arrangement was the last.

Worst-Case Complexity Is O(n)

For one isolated call, the worst case is linear in the length of the sequence. The algorithm may have to scan almost the entire range from the right and reverse almost the entire suffix.

For example, the descending permutation 5 4 3 2 1 forces the function to examine the whole range and then reverse it back to ascending order. That is clearly O(n).

So if someone asks for the complexity of a single call, O(n) is the correct answer.

Why the Amortized Cost Is Constant

The amortized view is different. Over many consecutive permutations, the suffix that gets reversed is usually very short.

The last one element is always trivially descending. The last two elements are descending only some of the time. The probability that the last k elements are strictly descending drops roughly like 1 / k!.

That means long suffixes are exponentially rare. The expected suffix length stays bounded by a constant, so the average amount of work for:

• scanning backward
• finding the swap partner
• reversing the suffix

also stays bounded by a constant.

This is why the amortized complexity over iterating through all permutations is O(1) per call, even though a single unlucky call can still cost O(n).

Think in Terms of Total Work

Suppose you enumerate all permutations of n distinct values. There are n! calls. If each call truly cost O(n) in an average sense, the total work would look like O(n * n!).

But next_permutation is better behaved than that. The expensive full-suffix reversals happen only at special boundary points, while most transitions only touch a tiny suffix near the end. So the total work grows proportionally to the number of generated permutations, giving constant amortized cost per transition.

Common Pitfalls

One common mistake is mixing up worst-case and amortized complexity. Saying O(1) without qualification is wrong for an isolated call; saying O(n) without mentioning the amortized behavior misses the interesting part of the algorithm.

Another issue is assuming amortized O(1) means the function never scans far. It absolutely can. The claim is only about the long-run average across many consecutive calls.

It is also easy to forget that if the sequence contains duplicate values, the number of distinct permutations changes, but the per-call algorithmic behavior is still governed by the same suffix scan and reversal logic.

Summary

• A single call to std::next_permutation has worst-case complexity O(n).
• The work comes from scanning for the pivot, swapping, and reversing the suffix.
• Over a long run of consecutive permutations, long suffix reversals are rare.
• That rarity gives constant amortized cost per call.
• When answering complexity questions, state clearly whether you mean worst-case or amortized cost.