6.042/18.062J Mathematics for Computer Science March 16,2005
Srini Devadas and Eric Lehman
Notes for Recitation 11
1 The Quest
An explorer is trying to reach the Holy Grail,which she believes is located in a desert
shrine d days walk from the nearest oasis,In the desert heat,the explorer must drink
continuously,She can carry at most 1 gallon of water,which is enough for 1 day,However,
she is free to create water caches out in the desert,
For example,if the shrine were 2/3 of a day’s walk into the desert,then she could recover
the Holy Grail with the following strategy,She leaves the oasis with 1 gallon of water,
travels 1/3 day into the desert,caches 1/3 gallon,and then walks back to the oasis—
arriving just as her water supply runs out,Then she picks up another gallon of water at
the oasis,walks 1/3 day into the desert,tops off her water supply by taking the 1/3 gallon
in her cache,walks the remaining 1/3 day to the shine,grabs the Holy Grail,and then
walks for 2/3 of a day back to the oasis— again arriving with no water to spare,
But what if the shrine were located farther away?
(a) What is the most distant point that the explorer can reach and return from if she
takes only 1 gallon from the oasis.?
Solution,At best she can walk 1/2 day into the desert and then walk back,
(b) What is the most distant point the explorer can reach and return form if she takes
only 2 gallons from the oasis? No proof is required; just do the best you can,
Solution,The explorer walks 1/4 day into the desert,drops 1/2 gallon,then walks
home,Next,she walks 1/4 day into the desert,picks up 1/4 gallon from her cache,
walks an additional 1/2 day out and back,then picks up another 1/4 gallon from
her cache and walks home,Thus,her maximum distance from the oasis is 3/4 of a
day’s walk,
(c) What about 3 gallons? (Hint,First,try to establish a cache of 2 gallons plus enough
water for the walk home as far into the desert as possible,Then use this cache as a
springboard for your solution to the previous part.)
Solution,Suppose the explorer makes three trips 1/6 day into the desert,dropping
2/3 gallon off units each time,On the third trip,the cache has 2 gallons of water,
and the explorer still has 1/6 gallon for the trip back home,So,instead of returning
2 Recitation 11
immediately,she uses the solution described above to advance another 3/4 of a day
into the desert and then returns home,Thus,she reaches
1 1 1 11
+ + =
6 4 2 12
of a days’ walk into the desert,
(d) How can the explorer go as far as possible is she withdraws n gallons of water?
Express your answer in terms of the Harmonic number H
n
,de?ned by,
1 1 1 1
H
n
= + +
1 2 3
+ ···
n
Solution,With n gallons of water,the explorer can reach a point H
n
/2 days into the
desert,
Suppose she makes n trips 1/(2n) days into the desert,dropping off (n? 1)/n gal-
lons each time,Before she leaves the cache for the last time,she has n gallons plus
enough for the walk home,So she applies her (n? 1)-day strategy to go an addi-
tional H
n?1
/2 days into the desert and then returns home,Her maximum distance
from the oasis is then,
1
+
H
n?1
=
H
n
2n 2 2
(e) Use the fact that
H
n
～ ln n
to approximate your previous answer in terms of logarithms.
Solution,An approximate answer is (ln n)/2.
(f) Suppose that the shrine is d = 10 days walk into the desert,Relying on your ap-
proximate answer,how many days must the explorer travel to recover the Holy
Grail?
Solution,She obtains the Grail when,
H
n
ln n
≥ 10
2
≈
2
This requires about n ≥ e
20
= 4.8 ·10
8
days.
Recitation 11 3
2 Asymptotic notation
(a) Which of these symbols Θ O Ω o ω can go in these boxes?
2n + log n = (n)
Θ,O,Ω
log n = (n)
O,o
√
n = (log
300
n)
Ω,ω
n2
n
= (n)
Ω,ω
n
7
= (1.01
n
)
O,o
4 Recitation 11
(b) Indicate which of the following holds for each pair of functions f(n),g(n) in the table
below; k ≥ 1,? > 0,and c > 1 are constants,Be prepared to justify your answers,
f(n) g(n) f = O(g) f = o(g) g = O(f) g = o(f) f = Θ(g) f ～ g
2
n
2
n/2
√
n n
sin nπ/2
log(n!) log(n
n
)
n
k
c
n
log
k
n n
Solution,
f(n) g(n) f = O(g) f = o(g) g = O(f) g = o(f) f = Θ(g) f ～ g
2
n
2
n/2
no no yes yes no no
√
n n
sin nπ/2
no no no no no no
log(n!) log(n
n
) yes no yes no yes yes
n
k
c
n
yes yes no no no no
log
k
n n
yes yes no no no no
Following are some hints on deriving the table above,
2
n
(a)
2
n/2
= 2
n/2
grows without bound as n grows—it is not bounded by a constant,
(b) When n is even,then n
sin nπ/2
= 1,So,no constant times n
sin nπ/2
will be an upper
sin nπ/2
bound on
√
n as n ranges over even numbers,When n ≡ 1 mod 4,then n =
1
n = n,So,no constant times
√
n will be an upper bound on n
sin nπ/2
as n ranges
over numbers ≡ 1 mod 4,
(c)
log(n!) = log
√
2πn
n
e
n
± c
n
(1)
= log n + n(log n? 1) ± d
n
(2)
～ nlog n (3)
= log n
n
,
where a ≤ c
n
,d
n
≤ b for some constants a,b ∈ R and all n,Here equation (1)
follows by taking logs of Stirling’s formula,(2) follows from the fact that the log of
a product is the sum of the logs,and (3) follows because any constant,log n,and n
are all o(nlog n) and hence so is their sum,
(d) Polynomial growth versus exponential growth,
(e) Polylogarithmic growth versus polynomial growth,
5 Recitation 11
cheat sheet
De?nitions,Intuitively and precisely the notations mean the following,
f = Θ(g) f grows as fast as g There exists n
0
and c
1
,c
2
> 0 such that
f = O(g) f grows no faster than g
for all n > n
0
,c
1
g(n) ≤ |f(n)| ≤ c
2
g(n),
There exists n
0
and c > 0 such that
f = Ω(g) f grows no slower than g
for all n > n
0
,|f(n)| ≤ cg(n),
There exists n
0
and c > 0 such that
f = o(g) f grows slower than g
for all n > n
0
,cg(n) ≤ |f(n)|,
For all c > 0,there exists n
0
such that
f = ω(g)
f ～ g
f grows faster than g
f/g approaches 1
for all n > n
0
,|f(n)| ≤ cg(n),
For all c > 0,there exists n
0
such that
for all n > n
0
,cg(n) ≤ |f(n)|,
lim
n→∞
f(n)/g(n) = 1
Relationships,Some asymptotic relationships between functions imply others:
f = O(g) and f = Ω(g)? f = Θ(g) f = o(g)? f = O(g)
f = O(g)? g = Ω(f) f = ω(g)? f = Ω(g)
f = o(g)? g = ω(f) f ～ g? f = Θ(g)
Limits,If the lim
n→∞
f(n)/g(n) exists,it reveals a lot about the relationship of f and g,
lim
n→∞
f/g = 0,∞? f = Θ(g) lim
n→∞
f/g = 1 f ～ g
lim
n→∞
f/g =? f = O(g) lim
n→∞
f/g = 0? f = o(g)? ∞
lim
n→∞
f/g = 0? f = Ω(g) lim
n→∞
f/g = f = ω(g)? ∞?
In this context,L’Hospital’s Rule is often useful,
If lim
n→∞
f(n) = ∞ and lim
n→∞
g(n) = ∞,then lim
n→∞
f(n)
g(n)
= lim
n→∞
f
(n)
g
(n)
,
Logarithms vs,polynomials vs,exponentials,Everybody knows the following two facts:
polylogarithms grow slower than polynomials,for all a,b > 0,(ln n)
a
= o(n
b
),
polynomials grow slower than exponentials,for all b,c > 0,n
b
= o (1 + c)
n
,
Srini Devadas and Eric Lehman
Notes for Recitation 11
1 The Quest
An explorer is trying to reach the Holy Grail,which she believes is located in a desert
shrine d days walk from the nearest oasis,In the desert heat,the explorer must drink
continuously,She can carry at most 1 gallon of water,which is enough for 1 day,However,
she is free to create water caches out in the desert,
For example,if the shrine were 2/3 of a day’s walk into the desert,then she could recover
the Holy Grail with the following strategy,She leaves the oasis with 1 gallon of water,
travels 1/3 day into the desert,caches 1/3 gallon,and then walks back to the oasis—
arriving just as her water supply runs out,Then she picks up another gallon of water at
the oasis,walks 1/3 day into the desert,tops off her water supply by taking the 1/3 gallon
in her cache,walks the remaining 1/3 day to the shine,grabs the Holy Grail,and then
walks for 2/3 of a day back to the oasis— again arriving with no water to spare,
But what if the shrine were located farther away?
(a) What is the most distant point that the explorer can reach and return from if she
takes only 1 gallon from the oasis.?
Solution,At best she can walk 1/2 day into the desert and then walk back,
(b) What is the most distant point the explorer can reach and return form if she takes
only 2 gallons from the oasis? No proof is required; just do the best you can,
Solution,The explorer walks 1/4 day into the desert,drops 1/2 gallon,then walks
home,Next,she walks 1/4 day into the desert,picks up 1/4 gallon from her cache,
walks an additional 1/2 day out and back,then picks up another 1/4 gallon from
her cache and walks home,Thus,her maximum distance from the oasis is 3/4 of a
day’s walk,
(c) What about 3 gallons? (Hint,First,try to establish a cache of 2 gallons plus enough
water for the walk home as far into the desert as possible,Then use this cache as a
springboard for your solution to the previous part.)
Solution,Suppose the explorer makes three trips 1/6 day into the desert,dropping
2/3 gallon off units each time,On the third trip,the cache has 2 gallons of water,
and the explorer still has 1/6 gallon for the trip back home,So,instead of returning
2 Recitation 11
immediately,she uses the solution described above to advance another 3/4 of a day
into the desert and then returns home,Thus,she reaches
1 1 1 11
+ + =
6 4 2 12
of a days’ walk into the desert,
(d) How can the explorer go as far as possible is she withdraws n gallons of water?
Express your answer in terms of the Harmonic number H
n
,de?ned by,
1 1 1 1
H
n
= + +
1 2 3
+ ···
n
Solution,With n gallons of water,the explorer can reach a point H
n
/2 days into the
desert,
Suppose she makes n trips 1/(2n) days into the desert,dropping off (n? 1)/n gal-
lons each time,Before she leaves the cache for the last time,she has n gallons plus
enough for the walk home,So she applies her (n? 1)-day strategy to go an addi-
tional H
n?1
/2 days into the desert and then returns home,Her maximum distance
from the oasis is then,
1
+
H
n?1
=
H
n
2n 2 2
(e) Use the fact that
H
n
～ ln n
to approximate your previous answer in terms of logarithms.
Solution,An approximate answer is (ln n)/2.
(f) Suppose that the shrine is d = 10 days walk into the desert,Relying on your ap-
proximate answer,how many days must the explorer travel to recover the Holy
Grail?
Solution,She obtains the Grail when,
H
n
ln n
≥ 10
2
≈
2
This requires about n ≥ e
20
= 4.8 ·10
8
days.
Recitation 11 3
2 Asymptotic notation
(a) Which of these symbols Θ O Ω o ω can go in these boxes?
2n + log n = (n)
Θ,O,Ω
log n = (n)
O,o
√
n = (log
300
n)
Ω,ω
n2
n
= (n)
Ω,ω
n
7
= (1.01
n
)
O,o
4 Recitation 11
(b) Indicate which of the following holds for each pair of functions f(n),g(n) in the table
below; k ≥ 1,? > 0,and c > 1 are constants,Be prepared to justify your answers,
f(n) g(n) f = O(g) f = o(g) g = O(f) g = o(f) f = Θ(g) f ～ g
2
n
2
n/2
√
n n
sin nπ/2
log(n!) log(n
n
)
n
k
c
n
log
k
n n
Solution,
f(n) g(n) f = O(g) f = o(g) g = O(f) g = o(f) f = Θ(g) f ～ g
2
n
2
n/2
no no yes yes no no
√
n n
sin nπ/2
no no no no no no
log(n!) log(n
n
) yes no yes no yes yes
n
k
c
n
yes yes no no no no
log
k
n n
yes yes no no no no
Following are some hints on deriving the table above,
2
n
(a)
2
n/2
= 2
n/2
grows without bound as n grows—it is not bounded by a constant,
(b) When n is even,then n
sin nπ/2
= 1,So,no constant times n
sin nπ/2
will be an upper
sin nπ/2
bound on
√
n as n ranges over even numbers,When n ≡ 1 mod 4,then n =
1
n = n,So,no constant times
√
n will be an upper bound on n
sin nπ/2
as n ranges
over numbers ≡ 1 mod 4,
(c)
log(n!) = log
√
2πn
n
e
n
± c
n
(1)
= log n + n(log n? 1) ± d
n
(2)
～ nlog n (3)
= log n
n
,
where a ≤ c
n
,d
n
≤ b for some constants a,b ∈ R and all n,Here equation (1)
follows by taking logs of Stirling’s formula,(2) follows from the fact that the log of
a product is the sum of the logs,and (3) follows because any constant,log n,and n
are all o(nlog n) and hence so is their sum,
(d) Polynomial growth versus exponential growth,
(e) Polylogarithmic growth versus polynomial growth,
5 Recitation 11
cheat sheet
De?nitions,Intuitively and precisely the notations mean the following,
f = Θ(g) f grows as fast as g There exists n
0
and c
1
,c
2
> 0 such that
f = O(g) f grows no faster than g
for all n > n
0
,c
1
g(n) ≤ |f(n)| ≤ c
2
g(n),
There exists n
0
and c > 0 such that
f = Ω(g) f grows no slower than g
for all n > n
0
,|f(n)| ≤ cg(n),
There exists n
0
and c > 0 such that
f = o(g) f grows slower than g
for all n > n
0
,cg(n) ≤ |f(n)|,
For all c > 0,there exists n
0
such that
f = ω(g)
f ～ g
f grows faster than g
f/g approaches 1
for all n > n
0
,|f(n)| ≤ cg(n),
For all c > 0,there exists n
0
such that
for all n > n
0
,cg(n) ≤ |f(n)|,
lim
n→∞
f(n)/g(n) = 1
Relationships,Some asymptotic relationships between functions imply others:
f = O(g) and f = Ω(g)? f = Θ(g) f = o(g)? f = O(g)
f = O(g)? g = Ω(f) f = ω(g)? f = Ω(g)
f = o(g)? g = ω(f) f ～ g? f = Θ(g)
Limits,If the lim
n→∞
f(n)/g(n) exists,it reveals a lot about the relationship of f and g,
lim
n→∞
f/g = 0,∞? f = Θ(g) lim
n→∞
f/g = 1 f ～ g
lim
n→∞
f/g =? f = O(g) lim
n→∞
f/g = 0? f = o(g)? ∞
lim
n→∞
f/g = 0? f = Ω(g) lim
n→∞
f/g = f = ω(g)? ∞?
In this context,L’Hospital’s Rule is often useful,
If lim
n→∞
f(n) = ∞ and lim
n→∞
g(n) = ∞,then lim
n→∞
f(n)
g(n)
= lim
n→∞
f
(n)
g
(n)
,
Logarithms vs,polynomials vs,exponentials,Everybody knows the following two facts:
polylogarithms grow slower than polynomials,for all a,b > 0,(ln n)
a
= o(n
b
),
polynomials grow slower than exponentials,for all b,c > 0,n
b
= o (1 + c)
n
,
