Def: Upper/Lower Bound

• Upper bound $$f(n)$$: there exists an algorithm that takes at most $$f(n)$$ steps on any input of size $$n$$.

• Lower bound $$g(n)$$: for any algorithm there exists an input on which it takes at least $$g(n)$$ steps.

True Complexity?

• Should be measured in terms of the best possible worst-case guarantee achievable by any algorithm.
• True complexity is somewhere between $$g(n)$$ and $$f(n)$$.

Def: Comparison Model

• In the comparison model, we have an input consisting of $$n$$ items (typically in some initial order). An algorithm may compare two items (asking is $$a_i$$ > $$a_j$$ ?) at a cost of 1.
• Moving the items around is free. No other operations on the items are allowed (such as using them as indices, XORing them, etc).

Theorem: Lower bound for comparison-based sorting

• Any deterministic comparison-based sorting algorithm must perform at least $$\lg{n!}$$ comparisons to sort $$n$$ elements in the worst case.
• Specifically, for any deterministic comparison-based sorting algorithm $$A$$, for all $$n \geq 2$$ there exists an input $$I$$ of size $$n$$ such that $$A$$ makes at least $$lg(n!) = Ω(n log n)$$ comparisons to sort $$I$$.
• Note: $$n! \in [(n/e)^n, n^n]$$ => $$n\lg{n} - 1.443n < \lg{n!} < n\lg{n}$$

Def: Exchange Model

• an input consists of an array of $$n$$ items, and the only operation allowed on the items is to swap a pair of them at a cost of 1 step. All other (planning) work is free: in particular, the items can be examined and compared to each other at no cost.

• (Upper bound) $$n − 1$$ exchanges is sufficient.

• (Lower bound) In fact, $$n − 1$$ exchanges are necessary, in the worst case.
  • 1 circle to $$n$$ circle proof

Adversary Argument

• It is often helpful when thinking about algorithms to imagine a game where one player is the algorithm designer, trying to come up with a good algorithm for the problem, and its opponent (the adversary) is trying to come up with an input that will cause the algorithm to run slowly.
• An algorithm with good worst-case guarantees is one that performs well no matter what input the adversary chooses.