Transcript Set 10: Lower Bounds

CSCE 411
Design and Analysis of
Algorithms
Set 10: Lower Bounds
Dr. J. Michael Moore
Fall 2014
Based primarily on slides by Prof. Jennifer Welch
CSCE 411, Fall 2014: Set 10
1
What is a Lower Bound?




Provides information about the best possible
efficiency of ANY algorithm for a problem
Tells us whether we can improve an algorithm
or not
When lower bound is (asymptotically) the
same as the best upper bound (provided by
an algorithm), the bound is TIGHT
If there is a gap, there might be room for
improvement
CSCE 411, Fall 2014: Set 10
2
Lower Bound Proof Technique #1:
Trivial

Use size of input or output



Ex: Any algorithm to generate all permutations of n
elements requires time Ω(n!) because there are n!
outputs
Ex: Computing the product of two n-by-n matrices
requires time Ω(n2) because the output has n2
entries
Ex: Any TSP solution for n cities requires Ω(n2) time
because there are Θ(n2) inputs to be taken into
account.
CSCE 411, Fall 2014: Set 10
3
Lower Bound Proof Technique #2:
Information-Theoretic




Consider the amount of information that the
solution must provide
Show that each step of the algorithm can only
produce so much information
Uses mechanism of decision trees
Example next…
CSCE 411, Fall 2014: Set 10
4
Comparison-Based Sorting


We’ve seen mergesort, insertion sort, quicksort,
heapsort,…
All these algorithms are comparison-based




the behavior depends on relative values of keys, not
exact values
behavior on [1,3,2,4] is same as on [9,25,23,99]
Fastest of these algorithms is O(nlog n).
We will show that's the best you can get with
comparison-based sorting.
CSCE 411, Fall 2014: Set 10
5
Decision Tree





Consider any comparison based sorting algorithm
Represent its behavior on all inputs of a fixed size
with a decision tree
Each non-leaf tree node corresponds to the
execution of a comparison
Each non-leaf tree node has two children, one for
the case when the comparison is true and one for
false
Each leaf tree-node represents correct sorted order
for that path
CSCE 411, Fall 2014: Set 10
6
Decision Tree Diagram
first comparison:
check if ai ≤ aj
YES
second comparison
if ai ≤ aj : check if
ak ≤ al
YES
NO
third comparison
if ai ≤ aj and ak ≤ al :
check if ax ≤ ay
NO
YES
NO
second comparison
if ai > aj : check if
am ≤ ap
YES
NO
CSCE 411, Fall 2014: Set 10
7
Insertion Sort
for j := 2 to n to
key := a[j]
i := j-1
while i > 0 and a[i] > key do
a[i+1] := a[i]
i := i -1
endwhile
a[i+1] := key
endfor
CSCE 411, Fall 2014: Set 10
8
Insertion Sort for n = 3
a1 ≤ a2 ?
YES
NO
a2 ≤ a3 ?
YES
a1 ≤ a3 ?
NO
a1 ≤ a3 ?
a1 a2 a3
NO
YES
a2 a1 a3
YES
NO
a1 a3 a2
a3 a1 a2
a2 ≤ a3 ?
YES
NO
a2 a3 a1
CSCE 411, Fall 2014: Set 10
a3 a2 a1
9
Insertion Sort for n = 3
a1 ≤ a2 ?
YES
NO
a2 ≤ a3 ?
YES
a1 ≤ a3 ?
NO
a1 ≤ a3 ?
a1 a2 a3
NO
YES
a2 a1 a3
YES
NO
a1 a3 a2
a3 a1 a2
a2 ≤ a3 ?
YES
NO
a2 a3 a1
CSCE 411, Fall 2014: Set 10
a3 a2 a1
10
How Many Leaves?

Must be at least one leaf for each permutation of
the input



otherwise there would be a situation that was not correctly
sorted
Number of permutations of n keys is n!.
Idea: since there must be a lot of leaves, but each
decision tree node only has two children, tree
cannot be too shallow

depth of tree is a lower bound on running time
CSCE 411, Fall 2014: Set 10
11
Key Lemma
Height of a binary tree with n! leaves is
(n log n).
Proof: Maximum number of leaves in a binary
tree with height h is 2h.
h = 1,
21 leaves
h = 2, 22 leaves
h = 3, 23 leaves
CSCE 411, Fall 2014: Set 10
12
Proof of Lemma


Let h be height of decision tree.
Number of leaves in decision tree, which is n!, is at
most 2h.
2h ≥ n!
h ≥ log(n!)
= log(n(n-1)(n-2)…(2)(1))
≥ (n/2)log(n/2) by algebra
= (n log n)
CSCE 411, Fall 2014: Set 10
13
Finishing Up
Any binary tree with n! leaves has height
(n log n).
 Decision tree for any comparison-based
sorting algorithm on n keys has height
(n log n).
 Any comparison-based sorting algorithm has
at least one execution with (n log n)
comparisons
 Any comparison-based sorting algorithm has
(n log n) worst-case running time.

CSCE 411, Fall 2014: Set 10
14
Lower Bound Proof Technique #3:
Problem Reduction (Transformation)

We have already seen how to use problem
transformations in a “positive” way



use a pre-existing algorithm for one problem Q to
get an algorithm for another problem P
So an upper bound for Q helps us get an upper
bound for P
We can also use this idea in a “negative” way

use an already-known lower bound for P to get a
lower bound for Q (note change in direction!)
CSCE 411, Fall 2014: Set 10
15
Using a Transformation to Get an
Algorithm for P from an Algorithm for Q

Recall transforming problem P to problem Q:
1.
2.
3.

transform P-input to Q-input
run (known) Q-algorithm on Q-input
transform Q-output to P-output
If we have an algorithm for Q already, and
we can do steps 1 and 3, then we get an
algorithm for P

Ex: transform max-flow to LP
CSCE 411, Fall 2014: Set 10
16
Using a Transformation to Get an
Algorithm for P from an Algorithm for Q
P-algorithm
P-input
Q-input
transform
Tintransform
Q-output
Q-algorithm
TQ
P-output
transform
Touttransform
TP = TQ + (Tintransform + Touttransform)
= TQ + Ttransform
CSCE 411, Fall 2014: Set 10
17
Using a Transformation to get a Lower
Bound for Q from a Lower Bound for P

Transformation:
1.
2.
3.

transform P-input to Q-input
run any Q-algorithm on Q-input
transform Q-output to P-output
If we have a lower bound for P and if steps 1
and 2 can be done “quickly enough”, we get a
lower bound for Q
CSCE 411, Fall 2014: Set 10
18
Using a Transformation to Get a Lower
Bound for Q from a Lower Bound for P
P-algorithm
P-input
Q-input
transform
Q-output
Q-algorithm
Tintransform
TQ
P-output
transform
Touttransform
TP = TQ + Ttransform
If TP = Ω(X) and Ttransform = o(X), then TQ = Ω(X)
CSCE 411, Fall 2014: Set 10
19
Use Ω(n log n) Sorting Lower Bound to
Get Ω(n log n) Convex Hull Lower Bound



Idea: If we could solve convex hull faster
than Θ(n log n), then we could solve sorting
faster than Θ(n log n)
Need to figure out how to use a convex hull
“subroutine” to sort numbers
Key observation: given n numbers x1,…,xn,
the points (x1,x12),…,(xn,xn2) are on a parabola
and thus are corners of a convex region
CSCE 411, Fall 2014: Set 10
20
Transform Sorting to Convex Hull
1.
2.
3.
Given input x1,…,xn, compute
(x1,x12),…(xn,xn2)
Run a convex hull algorithm on
(x1,x12),…(xn,xn2), resulting in a
sequence of points Y
Return sequence of first coordinates in
Y, starting at point with smallest first
coordinate and wrapping around if
necessary
Note: the convex hull algorithm must be
comparison-based and must produce its
output points in counter-clockwise (or
clockwise) order
CSCE 411, Fall 2014: Set 10
1.
O(n)
2.
Ω(n log
n)
3.
O(n)
Ω(n log n)
21