CMPS 256 Problems, Spring 2008

CMPS 256: Advanced Algorithms and Data Structures Chapter 3 Exercises & Solutions Feb. 23, 2006 Spring 2005-06 Chiraz BenAbdelkader Exercise 1 5n2 + 100n 3n2 + 2 f = ?(g) log3(n2) lg(n3) f = ?(g) nlg4 3lg n f = ?(g) lg2n n1/2 f = ?(g) f g Compare the rate of growth of each pair of functions f and g below. Solution 5n2 + 100n 3n2 + 2 5/3 f = Θ(g) log3(n2) lg(n3) 2/3*lg3 f = Θ(g) nlg4 3lg n ∞ f = ω(g) lg2n n1/2 0 f = o(g) limn → ∞f(n)/g(n) f g Answer Exercise 2 True or false? f(n)=O(g(n)) ⇒ ⇒ f(n)+g(n)=ΩΩ(f(n)) If true, give a proof based on formal definitions of order notation. If false, give a counter example. Solution: True. There are many ways to prove this. Exercise 2 (Cont.) First proof method: Second proof method: ( ( )) ( ) ( ) 0 ( ) ( ) ( ) lim 0 1 ( ) ( ) lim 0 1 ( ) ( ) lim 0 ( ) ( ) lim ( ( )) ( ) ( ( )) ) ( f n f n g n f n f n g n f n n g f n g n f n g n f n g n O g n n f n n n n = Ω + ⇔ > + ⇒ >     + ⇒ + >    ⇒  > ⇔ = Ω ⇔ = →∞ ∞ → →∞ ∞ → ( ( )) is closed under addition) ( ( )) ( ( ) ) ( ( ( )) ( ) Also, ( ( )) (transpose symmetry) ( ) ( ( )) ) ( f n f n g n n f f n n f f n g n O g n n f Ω = Ω + ∴ Ω = = Ω ⇔ = Exercise 2 (Cont.) Third proof method: ( ( )) ( ) ( ) ( ), ' ( ) ( ) 0 | ,' ( ), )1 ( ( ) ( ) 0 | , ( ) ( ), ( ) 0 | , ( ), ( ) 0 | , ( ( )) ) ( 0 0 0 1 0 0 1 0 0 0 f n f n n g n n c f n f n g n n c n n f n f n g n n c n n f n g n n c n n cg n f n c n O g n n f c c = Ω + ⇔ ∀ ≥ ≥ + > ∃ ⇔ ∀ ≥ + ≥ + > ∃ ⇔ ∀ ≥ ≥ > ∃ ⇔ ∀ ≥ ≤ > ⇔ ∃ = Exercise 3 Order these functions asymptotically from slowest to fastest rate of growth: n n n n n n n n n n n n n n n n lg lg 3 6.0 2 4 / lg 1 999 .2 4 2 10. 100)! ( 9. / lg 8. 3lg 7. 6. lg /)! lg( 5. 5 4. 3. ) 20lg(5 2. lg 1. − + + Exercise 3 (Cont.) Solution Strategy: In any question of this form, first simplify each function as much as possible Typically, simplify to well-known functions such as polynomial, poly-log, exponential, or factorial Use following rules from formula sheet to sort functions Polynomials are easy to compare: for any a,b>0, if a>b then na=ω(nb) So are exponentials: for any a,b>1, if a>b then an=ω(bn) Also we know that: for any c>1, a>0, b>0 nn = ωω(n!) = ωω(cn) = ωω(nb) = ωω(logan) If cannot use any of these rules, compare functions by computing the limit of their ratio Exercise 3 (Cont.) First step: simplify functions whenever possible ( ) ) ) (based on the formula ( lg 10. 100)!) (( 100)! ( 9. / lg ) ( / lg 8. ) ( 3lg 7. ( ) 6. ( ) )) ( ( ) ( ) ( ) ( ( )) ( ) (because ( ) / lg ) ( lg lg /)! lg( 5. )1( (because this is a decreasing function! ) 5 4. ) ( 3. (lg ) 80 lg 20 lg 5 ) 20 lg(5 2. ) lg ( lg 1. log log lg lg lg 3 3 6.0 6.0 2 4 /lg 1 .2 999 999 .2 4 2 5.0 2 a n n n n b b n a n n n n n n n n n n n n n n h n g n h n f n g n f n n n n n n n n n n n n n n n n = Θ = − = Θ − Θ = = Θ + = Θ + = Θ ⇒ = Θ = Θ Θ = Θ = Θ = = Θ + = = Θ Exercise 3 (Cont.) Second step: separate the functions into homogeneous groups in increasing order of growth ( ) n n n n n n n n n n n lg 3 2 5.0 .2 999 6.0 lg / lg ) ) ( lg ( : Other 100)! ( : Factorials ls : None Exponentia ) ) ( ( ) ( s : Polynomial -logs : None Poly (lg ) Logarithms : )1( : Constants Θ Θ Θ − Θ Θ Θ Θ Θ Θ Exercise 3 (Cont.) Third step: sort the functions in each group Use theorems (in formula sheet); otherwise compute the limit of ratio of pairs of functions For example, we have the following: [ ] ( ) [ ] ( ) [ ] [ ] ⇒ = ⇒ =     − = − = = ∞ ⇒ = →∞ →∞ ∞ → →∞ ∞ → ) / lg (lg lg lg 0 lg 1 lglg 3 lim lg lglg lglg lim 3lg lg lg / lg lg lim lim lg lg / lg lim 3 lg lg 3 3 5. 2 2 5. 0 3 n n n n n n n n n n n n n n n n n n n n n n n n n ω ) lg ( / lg 2 0 5. 3 n n n n ω = ( ) /lg ) ( lg 3 lg n n n n = ω Exercise 4 Given two functions f(n) and g(n), let h(n) = max(f(n),g(n)) Prove that: h(n) = ΘΘ(f(n)+g(n)) Solution: Like in Exercise 2, you should use formal definitions of order notation in your proof. Hint: use this definition of Θ-notation h(n)=Θ(f(n)+g(n)) ⇔ ∃c1,c2,n0>0 | c1(g(n)+f(n)) ≤ h(n) ≤ c2(f(n)+g(n)) (to be finished as homework)