1.9 Lower Bounds

A lower bound states that every algorithm for a problem must perform at least a certain amount of work in some model of computation. It tells you what cannot be improved. Upper bounds come from algorithms. Lower bounds come from arguments about necessity.

For example, if an algorithm scans an unsorted array to find the maximum value, the linear-time algorithm gives an upper bound of $O(n)$ . A lower bound proves that no algorithm can do better than inspecting all $n$ elements in the worst case. Together, these bounds show that the problem has optimal time $\Theta(n)$ in the comparison model.

Problem

You have an algorithm with a known running time, but you need to know whether a faster algorithm might exist.

Solution

Prove that any correct algorithm must perform a minimum amount of work. Use the model of computation explicitly.

A lower-bound argument usually has this shape:

1. State the computational model.
2. Identify what information the algorithm must learn.
3. Show that fewer operations leave two valid inputs indistinguishable.
4. Conclude that any correct algorithm needs at least the stated number of operations.

The third step is the key. If two different inputs require different outputs, but the algorithm cannot distinguish them, then the algorithm cannot be correct on both.

Example: Maximum in an Unsorted Array

Problem:

Given an unsorted array A[0..n-1], return its maximum value.

Claim:

Any comparison-based algorithm must inspect every element in the worst case.

Argument:

Suppose an algorithm does not inspect position k. Then the algorithm sees the same values on two inputs that differ only at A[k].

In the first input, A[k] is small and does not affect the maximum. In the second input, A[k] is larger than every inspected value. Because the algorithm never reads A[k], it behaves identically on both inputs. It must return the same answer for both, but the correct maximum differs. Therefore the algorithm is wrong on at least one of the two inputs.

So every correct algorithm must inspect all $n$ elements in the worst case. The lower bound is $\Omega(n)$ .

Since the simple scan runs in $O(n)$ time, the problem is solved optimally in $\Theta(n)$ time.

Example: Searching an Unsorted Array

Problem:

Given an unsorted array A and a value x, decide whether x appears in A.

A worst-case lower bound is $\Omega(n)$ .

If an algorithm skips some position k, then there are two valid inputs that agree everywhere the algorithm looked. In one input, A[k] != x; in the other input, A[k] = x. The correct answers differ, but the algorithm cannot distinguish the inputs. Therefore every correct algorithm must examine every position in the worst case.

This explains why linear search is optimal for unsorted arrays under direct inspection.

Example: Comparison Sorting

In comparison sorting, the algorithm learns about the order of elements only by comparing pairs.

There are $n!$ possible input orderings. A correct sorting algorithm must distinguish among all of them. Each comparison has two outcomes, so a comparison tree of height $h$ has at most $2^h$ leaves.

To sort correctly, the tree must have at least $n!$ leaves:

2^h \ge n!

Taking logarithms gives:

h \ge \log_2(n!)

Using the standard estimate $\log_2(n!) = \Theta(n \log n)$ , every comparison sort has worst-case lower bound:

\Omega(n \log n)

This is why merge sort and heap sort are asymptotically optimal comparison sorts.

Common Lower-Bound Techniques

Technique	Main Idea	Typical Use
Adversary argument	An adversary chooses unseen input values to force more work	Search, maximum, selection
Decision tree	Count how many outcomes an algorithm must distinguish	Sorting, comparison problems
Reduction	Show that solving one problem faster would solve a known hard problem faster	Graphs, optimization, complexity
Information argument	Count how many bits of information the output requires	Encoding, sorting, communication
Output-size bound	The algorithm must spend time producing the output	Enumeration problems

Lower Bound vs Upper Bound

An upper bound says:

There exists an algorithm with this cost.

A lower bound says:

No algorithm in this model can have lower cost.

When they match, you have an optimal algorithm.

Upper Bound	Lower Bound	Conclusion
$O(n)$	$\Omega(n)$	$\Theta(n)$ optimal
$O(n \log n)$	$\Omega(n \log n)$	$\Theta(n \log n)$ optimal
$O(n^2)$	$\Omega(n)$	Faster algorithm may exist
$O(2^n)$	$\Omega(n)$	Gap remains large

Common Pitfalls

A lower bound depends on the model. Sorting has an $\Omega(n \log n)$ lower bound for comparison sorting, but counting sort can run in linear time when keys come from a bounded integer range. The model changed, so the lower bound changed.

A lower bound for one algorithm is not a lower bound for the problem. Saying “this algorithm must scan all elements” does not prove that every algorithm must do so.

A weak lower bound may still be true but not informative. Every algorithm that reads input has $\Omega(1)$ time, but that rarely helps.

A lower bound should be paired with a matching or near-matching upper bound when possible. The comparison is what tells you whether improvement remains plausible.

Takeaway

Lower bounds explain the limits of algorithmic improvement. They identify the work that any correct algorithm must perform under a stated model. When a lower bound matches an algorithm’s upper bound, the algorithm is asymptotically optimal.