Asymptotic analysis of algorithms

We begin with a preliminary example.

0.1. Example. (Sorting a list)   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.

0.2. Definition. (Comparison-cum-swap)   One may compare any two adjacent numbers, and, if they are in the wrong order, swap them.

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 $⟨𝑎,𝑏,𝑐⟩$. 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. $⟨𝑎,𝑏,𝑐⟩$,
2. $⟨𝑎,𝑐,𝑏⟩$,
3. $⟨𝑏,𝑎,𝑐⟩$,
4. $⟨𝑏,𝑐,𝑎⟩$,
5. $⟨𝑐,𝑎,𝑏⟩$, and
6. $⟨𝑐,𝑏,𝑎⟩$.

So, if there are only two comparison-cum-swaps, we will not be able to obtain the correct result in two of these cases.

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

0.3. Problem. (List-sorting)   Given a list of $𝑛$ numbers to sort, as a function of $𝑛$, how many comparison-cum-swaps do we need?

Similarly, other problems of arbitrary size can be posed.

0.4. Problem. (Travelling salesman)   Given $𝑛$ cities and the distances between them, what is the shortest path by which the salesman may visit each of them at least once?

0.5. Problem. (3-SAT)   Given a formula over $𝑛$ literals in conjunctive normal form each of whose clauses has at most three literals, is there a satisfying assignment?

A generalisation of the argument above in fact gives the answer to the question for sorting: approximately $𝑛log𝑛$ (?hoare1962.?) The complexity of 3-SAT is open, but widely conjectured to be exponential.

0.6. Note. (What does ‘approximately’ mean here?)  

0.7. Remark.   Asymptotic analysis makes this precise. Here we shall mostly follow Cormen et al. (Introduction: § 2.1).

0.8. Definition. (Tight bounds)   Given a monotonically non-decreasing function $𝑔:\mathbb{N}\to \mathbb{N}$, we write

$$\mathrm{\Theta }\left(𝑔\left(𝑛\right)\right)=\left\{𝑓\left(𝑛\right):\text{there exist positive constants}{𝑐}_1\text{,}{𝑐}_2,\text{and}{𝑛}_0\text{such that, for all}𝑛⩾{𝑛}_0\text{,}0⩽{𝑐}_1𝑔\left(𝑛\right)⩽𝑓\left(𝑛\right)⩽{𝑐}_2𝑔\left(𝑛\right)\right\}.$$

0.9. Example. (#{2n \in \Theta(n)})  

Proof. For all $𝑛⩾1$,

$$0⩽\frac{1}{2}\cdot 2𝑛⩽𝑛⩽𝑛⩽1\cdot 2𝑛.$$

0.10. Example. (#{n^3
ot\in \Theta(n^2)})  

Proof. Suppose otherwise; then ${𝑛}^3⩽{𝑐}_2{𝑛}^2$ for all $𝑛⩾{𝑛}_0$ as above, but this is contradictory if $𝑛>{𝑐}_2$.⁠$\square$

0.11. Definition. (Upper bounds)   Given a monotonically increasing function $𝑔:\mathbb{N}\to \mathbb{N}$, we write

$$𝑂\left(𝑔\left(𝑛\right)\right)=\left\{𝑓\left(𝑛\right):\text{there exist positive constants}𝑐\text{and}{𝑛}_0\text{such that, for all}𝑛⩾{𝑛}_0\text{,}0⩽𝑓\left(𝑛\right)⩽\left\{𝑐𝑔\left(𝑛\right)\right\}\right\}.$$

We can now restate the result of ?hoare1962.?

0.12. Proposition. (Quicksort II)   The task of sorting a list of $𝑛$ numbers takes $\mathrm{\Theta }\left(𝑛log𝑛\right)$ comparison-cum-swaps.