Consider a list of two numbers, and a task: to sort the list in ascending order.

We will assume that only one operation is permitted.

How many comparison-cum-swaps do we need, on a list of two numbers, to sort it in ascending order? Clearly: one. For instance: if the list is $⟨1,2⟩$, the comparison-cum-swap immediately shows that they are in ascending order, so we are done. Alternatively, if the list is $⟨5,2⟩$, the comparison-cum-swap immediately shows they are in the wrong order, they are swapped, and then we are done.

Suppose the list contains three elements: for instance, $⟨1,2,3⟩$. How many comparison-cum-swaps do we need? One isn’t enough; we’d only be able to consider two of the numbers, and so the third number would have no effect on the final putatively sorted list we produce. What about two?

Two might be enough to verify that a list is sorted, if we’re lucky. Given $⟨1,2,3⟩$, we need only observe that $1<2$ and $2<3$.

However, two is not enough, in general, to sort a list (rather than simply to check whether it is actually sorted). Consider: every comparison-cum-swap leads to at most two possible orderings of some list $⟨a,b,c⟩$. So if there are two comparison-cum-swaps, there are at most $2\times 2=4$ orderings the procedure yields. But there are in fact six possible correct orderings of the list:

1. $⟨a,b,c⟩$,
2. $⟨a,c,b⟩$,
3. $⟨b,a,c⟩$,
4. $⟨b,c,a⟩$,
5. $⟨c,a,b⟩$, and
6. $⟨c,b,a⟩$.

We can pose the question for a problem of arbitrary size.

Given $n$ cities and the distances between them, what is the shortest path by which the salesman may visit each of them at least once?

Given a formula over $n$ literals in conjunctive normal form each of whose clauses has at most three literals, is there a satisfying assignment?

Given a monotonically non-decreasing function $g:\mathbb{N}\to \mathbb{N}$, we write $$\mathrm{\Theta }(g(n))=\{f(n):\text{there exist positive constants }{c}_1\text{, }{c}_2,\text{ and }{n}_0\text{ such that, for all }n⩾n_0\text{, }0⩽c_{1}g(n)⩽f(n)⩽c_{2}g(n)\}.$$

Given a monotonically increasing function $g:\mathbb{N}\to \mathbb{N}$, we write $$O(g(n))=\{f(n):\text{there exist positive constants }c\text{ and }{n}_0\text{ such that, for all }n⩾n_0\text{, }0⩽f(n)⩽cg(n)\}.$$

The task of sorting a list of $n$ numbers takes $\mathrm{\Theta }(nlogn)$ comparison-cum-swaps.