PowerPoint Presentation
Lower Bounds
& Models of Computation
Jeff Edmonds
York University
COSC 3101
Lecture 8
Thinking about Algorithms Abstractly
1
Lower Bounds for Sorting using Information Theory
2
The Time Complexity of a Problem P
Merge, Quick, and Heap Sort can sort N numbers
using O(N log N) comparisons between the values.
Theorem: No algorithm can sort faster.
The Time Complexity of a Problem P:
The minimum time needed
by an algorithm to solve it.
3
The Time Complexity of a Problem P
The minimum time needed by an algorithm to solve it.
Problem P is computable in time Tupper(n)
if there is an algorithm A which
outputs the correct answer
in this much time
Eg: Sorting computable in Tupper(n) = O(n2) time.
$ A, ” I, A(I)=P(I) and Time(A,I) £ Tupper(|I|)
Upper Bound:
4
Understand Quantifiers!!!
One girl
Could be a separate girl for each boy.
Sam Mary
Bob Beth
John Marilin Monro
Fred Ann
Sam Mary
Bob Beth
John Marilin Monro
Fred Ann
Algorithm
Input
$ A, ” I, A(I)=P(I) and Time(A,I) £ Tupper(|I|)
5
The Time Complexity of a Problem P
The minimum time needed by an algorithm to solve it.
$ A, ” I, A(I)=P(I) and Time(A,I) £ Tupper(|I|)
” I, $ A, A(I)=P(I) and Time(A,I) £ Tupper(|I|)
What does this say?
True for any problem P and time Tupper.
Given fixed I. Its output is P(I).
Let AP(I) be the algorithm that outputs the string P(I).
6
The Time Complexity of a Problem P
The minimum time needed by an algorithm to solve it.
Time Tlower(n) is a lower bound for problem p
if no algorithm solve the problem faster.
There may be algorithms that give the correct answer
or run quickly on some inputs instance.
Lower Bound:
7
The Time Complexity of a Problem P
The minimum time needed by an algorithm to solve it.
Lower Bound:
Time Tlower(n) is a lower bound for problem p
if no algorithm solve the problem faster.
Eg: No algorithm can sort N values
in Tlower = sqrt(N) time.
But for every algorithm, there is at least one instance I for which either the algorithm gives the wrong answer or it runs in too much time.
” A, $ I, A(I) = P(I) or Time(A,I) ³ Tlower(|I|)
8
Understand Quantifiers!!!
One girl
Could be a separate girl for each boy.
Sam Mary
Bob Beth
John Marilin Monro
Fred Ann
Sam Mary
Bob Beth
John Marilin Monro
Fred Ann
Algorithm
Input
” A, $ I, A(I) = P(I) or Time(A,I) ³ Tlower(|I|)
9
$ A, ” I, A(I)=P(I) and Time(A,I) £ Tupper(|I|)
” A, $ I, A(I) ≠ P(I) or Time(A,I) ³ Tlower(|I|)
Lower Bound:
Upper Bound:
The Time Complexity of a Problem P
The minimum time needed by an algorithm to solve it.
“There is” and “there isn’t a faster algorithm”
are almost negations of each other.
10
$ A, ” I, A(I)=P(I) and Time(A,I) £ Tupper(|I|)
Upper Bound:
Prover-Adversary Game
I have an algorithm A that I claim works and is fast.
I win if A on input I gives
the correct output
in the allotted time.
Oh yeah, I have an input I for which it does not.
What we have been doing all along.
11
Lower Bound:
Prover-Adversary Game
I win if A on input I gives
the wrong output or
runs slow.
” A, $ I, [ A(I) = P(I) or Time(A,I) ³ Tlower(|I|)]
Proof by contradiction.
I have an algorithm A that I claim works and is fast.
Oh yeah, I have an input I for which it does not .
12
Lower Bound:
Prover-Adversary Game
” A, $ I, [ A(I) = P(I) or Time(A,I) ³ Tlower(|I|)]
I have an algorithm A that I claim works and is fast.
Lower bounds are very hard to prove, because I must consider every algorithm
no matter how strange.
13
The Yes/No Questions Game
I choose a number Î[1..N].
I ask you yes/no questions.
Time is the number of questions
asked in the worst case.
I answer.
I determine the number.
14
The Yes/No Questions Game
Upper Bound
6
Great!
15
The Yes/No Questions Game
Upper Bound
Time
N leaves
= # of questions
= height
= log2(N)
16
The Yes/No Questions Game
Lower Bound?
Time
N leaves
Is there a faster
algorithm?
Is the third bit 1?
If different
questions?
= # of questions
= height
= log2(N)
17
The Yes/No Questions Game
Lower Bound?
N leaves
Is there a faster
algorithm?
If it has a different
structure?
Best case
Worst case
Time
= # of questions
= height
= log2(N)
18
The Yes/No Questions Game
Lower Bound
Theorem: For every question strategy A,
with the worst case object I to ask about,
log2 N questions need to be asked
to determine one of N objects.
” A, $ I, A(I) = P(I) or Time(A,I) ³ log2 N
Proof: Prover/Adversary Game
19
Lower Bound Proof
Oh yeah, I have an input I for which it does not.
I have an algorithm A that
I claim works and is fast.
Two cases:
# output leaves < N
# output leaves ³ N
20
I have an algorithm A that
I claim works and is fast.
Man your algorithm does
not have N output leaves.
I win if A on input I gives
the wrong output or
requires log N questions.
Lower Bound Proof: case 1
I give a input I = 4
with missing output.
21
Good now your algorithm
has all N outputs as leaves.
It must have height ³ log N.
I win if A on input I gives
the wrong output or
requires log N questions.
I have an algorithm A that I claim works and is fast.
I give a input I = 5 at a deep leaf.
Lower Bound Proof: case 2
22
The Yes/No Questions Game
Lower Bound
Theorem: For every question strategy A,
with the worst case object I to ask about,
log2 N questions need to be asked
to determine one of N objects.
" A, $ I, A(I) = P(I) or Time(A,I) ³ log2 N
Proof: Prover/Adversary Game
End of Proof.
23
Communication Complexity
Or a obj Îa set of N objs.
Time is the number of bits
sent in the worst case.
I send you a stream of bits.
I determine the object.
I choose a number Î[1..N].
24
Communication Complexity
Upper Bound
6
Great!
25
Communication Complexity
Lower Bound
Theorem: For every communication strategy A,
with the worst case object I to communicate,
log2 N bits need to transmitted
to communicate one of N objects.
" A, $ I, A(I) = P(I) or Time(A,I) ³ log2 N
26
The Sorting Game
I choose a permutation of {1,2,3,…,N}.
I ask you yes/no questions.
Time is the number of questions
asked in the worst case.
I answer.
I determine the permuation.
27
Sorting
Upper Bound
b,c,a
Great!
28
Time
N! leaves
= # of questions
= height
= log2(N!)
Sorting
Upper Bound
29
N! = 1 × 2 × 3 × … × N/2 × … × N
N factors each at most N.
N/2 factors each at least N/2.
£ NN
N/2 £
N/2
Bounding log(N!)
N/2 log(N/2) £ log(N!) £ N log(N)
= Q(N log(N)).
30
Time
N! leaves
= # of questions
= height
= log2(N!)
= Q(N log(N)).
Is there a faster
algorithm?
Is the third bit of c 1?
If different
questions?
Sorting
Lower Bound
31
class InsertionSortAlgorithm {
for (int i = 1; i < a.length; i++) {
int j = i;
while ((j > 0) && (a[j-1] > a[i])) {
a[j] = a[j-1];
j–; }
a[j] = B; }}
Is there a faster algorithm?
If different model of computation?
Sorting
Lower Bound
32
Sorting
Lower Bound
Theorem: For every sorting algorithm A,
with the worst case input instance I,
Q(N log2 N) comparisons (or other bit operations)
need to be executed to sort N objects.
” A, $ I, A(I) = P(I) or Time(A,I) ³ N log2 N
Proof: Prover/Adversary Game
33
Lower Bound Proof
Oh yeah, I will find an input I
for which it does not.
I have an algorithm A that I claim works and is fast.
class InsertionSortAlgorithm {
for (int i = 1; i < a.length; i++) {
int j = i;
while ((j > 0) && (a[j-1] > a[i])) {
a[j] = a[j-1];
j–; }
a[j] = B; }}
34
Lower Bound Proof
I have an algorithm A that I claim works and is fast.
class InsertionSortAlgorithm {
for (int i = 1; i < a.length; i++) {
int j = i;
while ((j > 0) && (a[j-1] > a[i])) {
a[j] = a[j-1];
j–; }
a[j] = B; }}
But first let me translate your algorithm into a decision tree.
35
I choose a permutation of {1,2,3,…,N}.
I answer.
I determine the permuation.
class InsertionSortAlgorithm {
for (int i = 1; i < a.length; i++) {
int j = i;
while ((j > 0) && (a[j-1] > a[i])) {
a[j] = a[j-1];
j–; }
a[j] = B; }}
I ask you this yes/no question.
I run my algorithm until
I need to know something about the input permutation.
Lower Bound Proof
36
class InsertionSortAlgorithm {
for (int i = 1; i < a.length; i++) {
int j = i;
while ((j > 0) && (a[j-1] > a[i])) {
a[j] = a[j-1];
j–; }
a[j] = B; }}
Lower Bound Proof
37
Lower Bound Proof
Oh yeah, I have an input I for which it does not.
I have an algorithm A that
I claim works and is fast.
Two cases:
# output leaves < N!
# output leaves ³ N!
38
I have an algorithm A that
I claim works and is fast.
Man your algorithm does
not have N! output leaves.
I win if A on input I gives
the wrong output or
requires log N questions.
Lower Bound Proof: case 1
I give a input I =
with missing output.
39
Good now your algorithm
has all N! outputs as leaves.
It must have height ³ log N!.
I win if A on input I gives
the wrong output or
requires log N! questions.
I have an algorithm A that I claim works and is fast.
Lower Bound Proof: case 2
I give a input I =
= Q(N log(N)).
40
Sorting
Lower Bound
Theorem: For every sorting algorithm A,
on the worst case input instance I,
Q(N log2 N) comparisons (or other bit operations)
need to be executed to sort N objects.
” A, $ I, A(I) = P(I) or Time(A,I) ³ N log2 N
Proof: Prover/Adversary Game
End of Proof.
41
End
42
$
”
g
b
loves
b
g
,
,
(
,
)
”
$
b
g
loves
b
g
,
,
(
,
)
/docProps/thumbnail.jpeg