6.042/18.] Mathematics for Computer Science March 16, 2005 Srini devadas and Eric Lehman Notes for Recitation 11 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 days 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 return 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 walk home.Next, she walks 1/4 day into the desert picks up 1/4 gallet l(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
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
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 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 Hn, defined by 111 Hn 123 Solution. With n gallons of water, the explorer can reach a point Hn/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 Hn-1/2 days into the desert and then returns home. Her maximum distance from the oasis is then: 1 H (e) Use the fact that Hn wInn to approximate your previous answer in terms of logarithms Solution. An approximate answer is(In 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 This requires about n≥e20=4.8·10 days
Recitation 11 2 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 Hn, defined by: 1 1 1 1 Hn = + + 1 2 3 + · · · n Solution. With n gallons of water, the explorer can reach a point Hn/2 days into the desert. Suppose she makes n trips 1/(2n) days into the desert, dropping off (n − 1)/n gallons 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 additional Hn−1/2 days into the desert and then returns home. Her maximum distance from the oasis is then: 1 + Hn−1 = Hn 2n 2 2 (e) Use the fact that Hn ∼ 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 approximate answer, how many days must the explorer travel to recover the Holy Grail? Solution. She obtains the Grail when: Hn ln n ≥ 10 2 ≈ 2 This requires about n ≥ e20 = 4.8 · 108 days
Recitation 11 2 Asymptotic notation (a)Which of these symbol 6O90d can go in these boxes? 2n + logn 6.O.g log n log-300 1.01n
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 = (log300 n) Ω, ω n2n = (n) Ω, ω n7 = (1.01n) O, o
Recitation 11 (b)Indicate which of the following holds for each pair of functions f(m),g(n)in the table below;k> 1,E>0, and c>l are constants. Be prepared to justify your answers f(a)9G)f=oo|=o|9=O|g=o)f=6o|f~9 2 SIn n7 log(n! )log(n") Solution f(m)g(n)f=O(g)f=o(g)g=o9=0f=6(gf~g log(n!) log(n yes Following are some hints on deriving the table above (a)on/2 2n/ grows without bound as n grows-it is not bounded by a constant (b) When n is even, then n sinn/2= 1. So, no constant times n sin n /2 will be an uppe bound on Vn as n ranges over even numbers. When n= l mod 4, then nsin nr/> n=n. So, no constant times Vn will be an upper bound on nsin n/ as n ranges oⅴ er numbers≡1mod4. log(nl!)=logv2丌n +n(logn-1)±dn n where a≤cn,dln≤ b for some constants a,b∈ R and all n. equation(1) follows by taking logs of Stirlings 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 are all o(n log n) and hence so is their sum (d)Polynomial growth versus exponential growth (e) Polylogarithmic growth versus polynomial growth
� � Recitation 11 4 (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 2n 2n/2 √n nsin nπ/2 log(n!) log(nn) nk cn logk n n� Solution. f(n) g(n) f = O(g) f = o(g) g = O(f) g = o(f) f = Θ(g) f ∼ g 2n 2n/2 no no yes yes no no √n nsin nπ/2 no no no no no no log(n!) log(nn) yes no yes no yes yes nk cn yes yes no no no no logk n n� yes yes no no no no Following are some hints on deriving the table above: 2n (a) 2n/2 = 2n/2 grows without bound as n grows—it is not bounded by a constant. (b) When n is even, then nsin nπ/2 = 1. So, no constant times nsin 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 nsin nπ/2 as n ranges over numbers ≡ 1 mod 4. (c) log(n!) = log √ 2πn n e n ± cn (1) = log n + n(log n − 1) ± dn (2) ∼ n log n (3) = log nn. where a ≤ cn, dn ≤ 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(n log n) and hence so is their sum. (d) Polynomial growth versus exponential growth. (e) Polylogarithmic growth versus polynomial growth
Recitation 11 cheat sheet Definitions. Intuitively and precisely the notations mean the following ∫=6(g)∫ grows as fast as g There exists no and c1, c2>0 such that for all n>mo:ag(m)≤|f(m)≤eg(m) f=O(g) f grows no faster than g There exists no and c >0 such that for all n> no: f(n)l s cg(n) f=Q(g) f grows no slower than g There exists no and c>0 such that (n)≤|f(m) f=o(g) f grows slower than g For all c>0, there exists no such that for all n>no: If(n)ls cg(n) f=w(g)f grows faster than g For all c>0, there exists no such that for all n>no: cg(n)0, (Inn)=o(no) polynomials grow slower than exponentials: for all b, c>0, nb=o((1+cn)
� � Recitation 11 5 cheat sheet Definitions. Intuitively and precisely the notations mean the following: f = Θ(g) f grows as fast as g There exists n0 and c1, c2 > 0 such that f = O(g) f grows no faster than g for all n > n0: c1g(n) ≤ |f(n)| ≤ c2g(n). There exists n0 and c > 0 such that f = Ω(g) f grows no slower than g for all n > n0: |f(n)| ≤ cg(n). There exists n0 and c > 0 such that f = o(g) f grows slower than g for all n > n0: cg(n) ≤ |f(n)|. For all c > 0, there exists n0 such that f = ω(g) f ∼ g f grows faster than g f /g approaches 1 for all n > n0: |f(n)| ≤ cg(n). For all c > 0, there exists n0 such that for all n > n0: cg(n) ≤ |f(n)|. limn→∞ 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 limn→∞ f(n)/g(n) exists, it reveals a lot about the relationship of f and g: limn→∞ f/g =� 0,∞ ⇒ f = Θ(g) limn→∞ f/g = 1 ⇒ f ∼ g limn→∞ f/g =� ∞ ⇒ f = O(g) limn→∞ f/g = 0 ⇒ f = o(g) limn→∞ f/g =� 0 ⇒ f = Ω(g) limn→∞ f/g = ∞ ⇒ f = ω(g) In this context, L’Hospital’s Rule is often useful: If limn→∞ f(n) = ∞ and limn→∞ g(n) = ∞, then limn→∞ f(n) g(n) = limn→∞ 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(nb ). • polynomials grow slower than exponentials: for all b, c > 0, nb = o (1 + c)n