Algorithms

Lecture 12: Lower Bounds [Fa’13]

It was a Game called Yes and No, where Scrooge’s nephew had to think of something, and the rest
must find out what; he only answering to their questions yes or no, as the case was. The brisk
fire of questioning to which he was exposed, elicited from him that he was thinking of an animal,
a live animal, rather a disagreeable animal, a savage animal, an animal that growled and grunted
sometimes, and talked sometimes, and lived in London, and walked about the streets, and wasn’t
made a show of, and wasn’t led by anybody, and didn’t live in a menagerie, and was never killed
in a market, and was not a horse, or an ass, or a cow, or a bull, or a tiger, or a dog, or a pig, ora cat, or a bear. At every fresh question that was put to him, this nephew burst into a fresh roar oflaughter; and was so inexpressibly tickled, that he was obliged to get up off the sofa and stamp. At
last the plump sister, falling into a similar state, cried out :“ I have found it out ! I know what it is, Fred ! I know what it is !”“ What is it ?” cried Fred.
“ It’s your Uncle Scro-o-o-o-oge !”Which it certainly was. Admiration was the universal sentiment, though some objected thatthe reply to “ Is it a bear?” ought to have been “Yes;" inasmuch as an answer in the negative
was sufficient to have diverted their thoughts from Mr Scrooge, supposing they had ever had any
tendency that way.
— Charles Dickens, A Christmas Carol (1843)

12

Lower Bounds

12.1

Huh? Whuzzat?

So far in this class we’ve been developing algorithms and data structures to solve certain problems
as quickly as possible. Starting with this lecture, we’ll turn the tables, by proving that certain
problems cannot be solved as quickly as we might like them to be.
Let TA(X ) denote the running time of algorithm A given input X . For most of the semester,
we’ve been concerned with the the worst-case running time of A as a function of the input size:
TA(n) := max TA(X ).
|X |=n

The worst-case complexity of a problem Π is the worst-case running time of the fastest algorithm
for solving it:TΠ (n) := min TA(n) = min
max TA(X ).
A solves Π

A solves Π |X |=n

Any algorithm A that solves Π immediately implies an upper bound on the complexity of Π; theinequality TΠ (n) ≤ TA (n) follows directly from the definition of TΠ . Just as obviously, faster
algorithms give us better (smaller) upper bounds. In other words, whenever we give a running
time for an algorithm, what we’re really doing—and what most computer scientists devote their
entire careers doing1—is bragging about how easy some problem is.
Now, instead of bragging about how easy problems are, we will argue that certain problems
are hard, by proving lower bounds on their complexity. This is considerably harder than proving
1This sometimes leads to long sequences of results that sound like an obscure version of “Name that Tune”:
Lennes: “I can triangulate that polygon in O(n2 ) time.”
Shamos: “I can triangulate that polygon in O(n log n) time.”
Tarjan: “I can triangulate that polygon in O(n log log n) time.”
Seidel: “I can triangulate that polygon in O(n log∗ n) time.” [Audience gasps.]
Chazelle: “I can triangulate that polygon in O(n) time.” [Audience gasps and applauds.]“Triangulate that polygon!”© Copyright 2018 Jeff Erickson.
This work is licensed under a Creative Commons License (http://creativecommons.org/licenses/by-nc-sa/4.0/).
Free distribution is strongly encouraged; commercial distribution is expressly forbidden.
See http://jeffe.cs.illinois.edu/teaching/algorithms/ for the most recent revision.

1

Algorithms

Lecture 12: Lower Bounds [Fa’13]

an upper bound, because it’s no longer enough to examine a single algorithm. To prove an
inequality of the form TΠ (n) = Ω( f (n)), we must prove that every algorithm that solves Π has aworst-case running time Ω( f (n)), or equivalently, that no algorithm runs in o( f (n)) time.

12.2

Decision Trees

Unfortunately, there is no formal definition of the phrase ‘all algorithms’!2 So when we derive
lower bounds, we first have to specify precisely what kinds of algorithms we will consider andprecisely how to measure their running time. This specification is called a model of computation.
One rather powerful model of computation—and the only model we’ll talk about in thislecture—is the decision tree model. A decision tree is, as the name suggests, a tree. Each internal
node in the tree is labeled by a query, which is just a question about the input. The edges out ofa node correspond to the possible answers to that node’s query. Each leaf of the tree is labeledwith an output. To compute with a decision tree, we start at the root and follow a path down toa leaf. At each internal node, the answer to the query tells us which node to visit next. When wereach a leaf, we output its label.
For example, the guessing game where one person thinks of an animal and the other persontries to figure it out with a series of yes/no questions can be modeled as a decision tree. Eachinternal node is labeled with a question and has two edges labeled ‘yes’ and ‘no’. Each leaf islabeled with an animal.
Does it live in the water?
NO

S

YE

Does it have wings?

spider

gnu

NO

NO

fly

Does it have wings?
S

frog

NO

YE

S

YE

YE
S

YE

fish

Does it have more than four legs?

NO

S

Does it have scales?

eagle

A decision tree to choose one of six animals.

Here’s another simple and familiar example, called the dictionary problem. Let A be a fixedarray with n numbers. Suppose we want to determine, given a number x, the position of x
in the array A, if any. One solution to the dictionary problem is to sort A (remembering every
element’s original position) and then use binary search. The (implicit) binary search tree can beused almost directly as a decision tree. Each internal node in the search tree stores a key k; thecorresponding node in the decision tree stores the question ‘Is x < k?’. Each leaf in the searchtree stores some value A[i]; the corresponding node in the decision tree asks ‘Is x = A[i]?’ andhas two leaf children, one labeled ‘i’ and the other ‘none’.
We define the running time of a decision tree algorithm for a given input to be the number ofqueries in the path from the root to the leaf. For example, in the ‘Guess the animal’ tree above,
2Complexity-theory snobs purists sometimes argue that ‘all algorithms’ is just a synonym for ‘all Turing machines’.
This is utter nonsense; Turing machines are just another model of computation. Turing machines might be a reasonable
abstraction of physically realizable computation—that’s the Church-Turing thesis—but it has a few problems. First,
computation is an abstract mathematical process, not a physical process. Algorithms that use physically unrealistic
components (like exact real numbers, or unbounded memory) are still mathematically well-defined and still provide
useful intuition about real-world computation. Moreover, Turing machines don’t accurately reflect the complexity ofphysically realizable algorithms, because (for example) they can’t do arithmetic or access arbitrary memory locations
in constant time. At best, they estimate algorithmic complexity up to polynomial factors (although even that is
unknown).

2

Algorithms

x<11?

7 11 13 17 19

NO

YES

x<5?

4

-

5

-

6

-

YES

S
YE

YES

-

YES

S
YE

YES

YES

YE

YES

3

x=19?

NO

-

NO

2

x=17?

NO

-

x=13?
NO

1

x<19?

NO

19

x=11?
NO

17

x=7?

NO

13

x=5?

x<13?

NO

11

x=3?

NO

7

x=2?

NO

5

19

x<7?

NO

3

13

NO

2

7

NO

S
YE

x<3?

17
S

5

3

x<17?
NO

S

YE

YES

11

S

5

YE

3

YES

2

Lecture 12: Lower Bounds [Fa’13]

7

-

8

-

Left: A binary search tree for the first eight primes.
Right: The corresponding binary decision tree for the dictionary problem (- = ‘none’).

T (frog) = 2. Thus, the worst-case running time of the algorithm is just the depth of the tree. Thisdefinition ignores other kinds of operations that the algorithm might perform that have nothing
to do with the queries. (Even the most efficient binary search problem requires more than one
machine instruction per comparison!) But the number of decisions is certainly a lower bound on
the actual running time, which is good enough to prove a lower bound on the complexity of aproblem.
Both of the examples describe binary decision trees, where every query has only two answers.
We may sometimes want to consider decision trees with higher degree. For example, we mightuse queries like ‘Is x greater than, equal to, or less than y?’ or ‘Are these three points in clockwiseorder, colinear, or in counterclockwise order?’ A k-ary decision tree is one where every query has(at most) k different answers. From now on, I will only consider k-ary decision trees where
k is a constant.

12.3

Information Theory

Most lower bounds for decision trees are based on the following simple observation: The answers
to the queries must give you enough information to specify any possible output. If a problem
has N different outputs, then obviously any decision tree must have at least N leaves. (It’spossible for several leaves to specify the same output.) Thus, if every query has at most k possible
answers, then the depth of the decision tree must be at least dlogk N e = Ω(log N ).
Let’s apply this to the dictionary problem for a set S of n numbers. Since there are n + 1
possible outputs, any decision tree must have at least n + 1 leaves, and thus any decision tree
must have depth at least dlogk (n + 1)e = Ω(log n). So the complexity of the dictionary problem,in the decision-tree model of computation, is Ω(log n). This matches the upper bound O(log n)that comes from a perfectly-balanced binary search tree. That means that the standard binary
search algorithm, which runs in O(log n) time, is optimal—there is no faster algorithm in thismodel of computation.

12.4

But wait a second. . .

We can solve the membership problem in O(1) expected time using hashing. Isn’t this inconsistent
with the Ω(log n) lower bound?
No, it isn’t. The reason is that hashing involves a query with more than a constant number ofoutcomes, specifically ‘What is the hash value of x?’ In fact, if we don’t restrict the degree of thedecision tree, we can get constant running time even without hashing, by using the obviously
unreasonable query ‘For which index i (if any) is A[i] = x?’. No, I am not cheating — rememberthat the decision tree model allows us to ask any question about the input!
3

Algorithms

Lecture 12: Lower Bounds [Fa’13]

This example illustrates a common theme in proving lower bounds: choosing the right modelof computation is absolutely crucial. If you choose a model that is too powerful, the problem
you’re studying may have a completely trivial algorithm. On the other hand, if you consider more
restrictive models, the problem may not be solvable at all, in which case any lower bound will bemeaningless! (In this class, we’ll just tell you the right model of computation to use.)

12.5

Sorting

Now let’s consider the classical sorting problem — Given an array of n numbers, arrange them inincreasing order. Unfortunately, decision trees don’t have any way of describing moving dataaround, so we have to rephrase the question slightly:
Given a sequence 〈x 1 , x 2 , . . . , x n 〉 of n distinct numbers, find the permutation π suchthat x π(1) < x π(2) < · · · < x π(n) .
Now a k-ary decision-tree lower bound is immediate. Since there are n! possible permutations π,
any decision tree for sorting must have at least n! leaves, and so must have depth Ω(log(n!)). To
simplify the lower bound, we apply Stirling’s approximation   n n n pn1n! =.
2πn 1 + Θ>eneThis gives us the lower bound n n m  llogk (n!) > logk
= n logk n − n logk e = Ω(n log n).
eThis matches the O(n log n) upper bound that we get from mergesort, heapsort, or quicksort, so
those algorithms are optimal. The decision-tree complexity of sorting is Θ(n log n).
Well. . . we’re not quite done. In order to say that those algorithms are optimal, we haveto demonstrate that they fit into our model of computation. A few minutes of thought willconvince you that they can be described as a special type of decision tree called a comparison
tree, where every query is of the form ‘Is x i bigger or smaller than x j ?’ These algorithms treat
any two input sequences exactly the same way as long as the same comparisons produce exactly
the same results. This is a feature of any comparison tree. In other words, the actual input
values don’t matter, only their order. Comparison trees describe almost all well-known sorting
algorithms: bubble sort, selection sort, insertion sort, shell sort, quicksort, heapsort, mergesort,and so forth—but not radix sort or bucket sort.

12.6

Finding the Maximum and Adversaries

Finally let’s consider the maximum problem: Given an array X of n numbers, find its largest
entry. Unfortunately, there’s no hope of proving a lower bound in this formulation, since there
are an infinite number of possible answers, so let’s rephrase it slightly.
Given a sequence 〈x 1 , x 2 , . . . , x n 〉 of n distinct numbers, find the index m such thatx m is the largest element in the sequence.
We can get an upper bound of n − 1 comparisons in several different ways. The easiest
is probably to start at one end of the sequence and do a linear scan, maintaining a current
maximum. Intuitively, this seems like the best we can do, but the information-theoretic bound is4

Algorithms

Lecture 12: Lower Bounds [Fa’13]

only dlog2 ne. And in fact, this bound is tight! We can locate the maximum element by asking
only dlog2 ne ‘unreasonable’ questions like “Is the index of the maximum element odd?” No, thisis not cheating—the decision tree model allows arbitrary questions.
To prove a non-trivial lower bound for this problem, we must do two things. First, we needto consider a more reasonable model of computation, by restricting the kinds of questions thealgorithm is allowed to ask. We will consider the comparison tree model, where every querymust have the form “Is x i > x j ?”. Since most algorithms3 for finding the maximum rely oncomparisons to make control-flow decisions, this does not seem like an unreasonable restriction.
Second, we will use something called an adversary argument. The idea is that an allpowerful malicious adversary pretends to choose an input for the algorithm. When the algorithm
asks a question about the input, the adversary answers in whatever way will make the algorithm
do the most work. If the algorithm does not ask enough queries before terminating, then there
will be several different inputs, each consistent with the adversary’s answers, that should resultin different outputs. In this case, whatever the algorithm outputs, the adversary can ‘reveal’ an
input that is consistent with its answers, but contradicts the algorithm’s output, and then claimthat that was the input that he was using all along.
For the maximum problem, the adversary originally pretends that x i = i for all i, and answers
all comparison queries accordingly. Whenever the adversary reveals that x i < x j , he marks x i as
an item that the algorithm knows (or should know) is not the maximum element. At most one
element x i is marked after each comparison. Note that x n is never marked. If the algorithm
does less than n − 1 comparisons before it terminates, the adversary must have at least one otherunmarked element x k 6= x n . In this case, the adversary can change the value of x k from k ton + 1, making x k the largest element, without being inconsistent with any of the comparisonsthat the algorithm has performed. In other words, the algorithm cannot tell that the adversary
has cheated. However, x n is the maximum element in the original input, and x k is the largest
element in the modified input, so the algorithm cannot possibly give the correct answer for bothcases. Thus, in order to be correct, any algorithm must perform at least n − 1 comparisons.
The adversary argument we described has two very important properties. First, no algorithm
can distinguish between a malicious adversary and an honest user who actually chooses an input
in advance and answers all queries truthfully. But much more importantly, the adversary makes
absolutely no assumptions about the order in which the algorithm performs comparisons.
The adversary forces any comparison-based algorithm⁴ to either perform n − 1 comparisons, or
to give the wrong answer for at least one input sequence.

Exercises
0. Simon bar Kokhba thinks of an integer between 1 and 1,000,000 (or so he claims). You aretrying to determine his number by asking as few yes/no questions as possible. How many
yes/no questions are required to determine Simon’s number in the worst case? Give bothan upper bound (supported by an algorithm) and a lower bound.
1. Consider the following multi-dictionary problem. Let A[1 .. n] be a fixed array of distinct
integers. Given an array X [1 .. k], we want to find the position (if any) of each integer
3but not all—see Exercise ??
⁴In fact, the n − 1 lower bound for finding the maximum holds in a more powerful model called algebraic decision
trees, which are binary trees where every query is a comparison between two polynomial functions of the input values,
such as ‘Is x 12 − 3x 2 x 3 + x 417 bigger or smaller than 5 + x 1 x 35 x 52 − 2x 742 ?’5

Algorithms

Lecture 12: Lower Bounds [Fa’13]

X [i] in the array A. In other words, we want to compute an array I[1 .. k] where for each i,either I[i] = 0 (so zero means ‘none’) or A[I[i]] = X [i]. Determine the exact complexityof this problem, as a function of n and k, in the binary decision tree model.
2. We say that an array A[1 .. n] is k-sorted if it can be divided into k blocks, each of size n/k,such that the elements in each block are larger than the elements in earlier blocks, andsmaller than elements in later blocks. The elements within each block need not be sorted.
For example, the following array is 4-sorted:
1

2

4

3

7

6

8

5

10

11

9

12

15

13

16

14

(a) Describe an algorithm that k-sorts an arbitrary array in O(n log k) time.
(b) Prove that any comparison-based k-sorting algorithm requires Ω(n log k) comparisonsin the worst case.
(c) Describe an algorithm that completely sorts an already k-sorted array in O(n log(n/k))time.
(d) Prove that any comparison-based algorithm to completely sort a k-sorted array
requires Ω(n log(n/k)) comparisons in the worst case.
In all cases, you can assume that n/k is an integer.
3. Recall the nuts-and-bolts problem from the lecture on randomized algorithms. We are
given n bolts and n nuts of different sizes, where each bolt exactly matches one nut. Our
goal is to find the matching nut for each bolt. The nuts and bolts are too similar to compare
directly; however, we can test whether any nut is too big, too small, or the same size as
any bolt.
(a) Prove that in the worst case, Ω(n log n) nut-bolt tests are required to correctly matchup the nuts and bolts.
(b) Now suppose we would be happy to find most of the matching pairs. Prove that in theworst case, Ω(n log n) nut-bolt tests are required even to find n/2 arbitrary matchingnut-bolt pairs.

? 4.

? (c)

Prove that in the worst case, Ω(n + k log n) nut-bolt tests are required to find karbitrary matching pairs. [Hint: Use an adversary argument for the Ω(n) term.]? (d)Describe a randomized algorithm that finds k matching nut-bolt pairs in O(n + k log n)
expected time.

Suppose you want to determine the largest number in an n-element set X = {x 1 , x 2 , . . . , x n },where each element x i is an integer between 1 and 2m − 1. Describe an algorithm thatsolves this problem in O(n + m) steps, where at each step, your algorithm compares one of
the elements x i with a constant. In particular, your algorithm must never actually compare
two elements of X ! [Hint: Construct and maintain a nested set of ‘pinning intervals’ forthe numbers that you have not yet removed from consideration, where each interval but
the largest is either the upper half or lower half of the next larger block.]© Copyright 2018 Jeff Erickson.
This work is licensed under a Creative Commons License (http://creativecommons.org/licenses/by-nc-sa/4.0/).
Free distribution is strongly encouraged; commercial distribution is expressly forbidden.
See http://jeffe.cs.illinois.edu/teaching/algorithms for the most recent revision.

6