CS333 Assignment 1Instructor: KD [email protected] Name:• This homework is due at the beginning of the class on February 26, 2008. Timely submissionof your homework is recommended, because there will be 10% late penalty per day.• Always try to be precise and concise. Finally, always print!1: [60 points] Prove the following using the Properties of Order in Section 1.4.2.(a) [10 points] 1, 000, 000n ∈ O(n2).For n ≥ 1, 106n ≤ 106n2. Thus, 106n ∈ O(n2).(b) [20 points] f(n) = n2+ 3n3+ n ∈ Θ(n3). [Hint: Show that f(n) ∈ O(n3) and f(n) ∈ Ω(n3).]1. Show that f(n) ∈ O(n3): For n ≥ 1, n2+ 3n3+ n ≤ 5n3. Thus, f(n) ∈ O(n3).2. Show f(n) ∈ Ω(n3): For n ≥ 0, n2+ 3n3+ n ≥ 3n3. Thus, f(n) = n2+ 3n3+ n ∈ Ω(n3).From 1 and 2, we conclude that f(n) = Θ(n3).(c) [20 points] p(n) =Pki=1aini∈ Θ(nk) where ai> 0.1. Show that p(n) ∈ O(nk): For n ≥ 1,Pki=1aini≤ (Pki=1ai) × nk. Hence, p(n) ∈ O(nk).2. Show that p(n) ∈ Ω(nk): For n ≥ 0,Pki=1aini≥ aknk. Thus, p(n) ∈ Ω(nk).(d) [10 points] n3∈ Ω(n): This is true because, for n ≥ 1, n3≥ 1 × n.2: [20 points] Prove the following using Theorem 1.3.(a)[10 points] n! ∈ ω(2n). [Hint: Refer to Example 1.26.]Suppose n = 2kfor some integer k > 0. (If n is not a power of 2, ⌊n/2⌋ instead of n/2 needs tobe considered.) Note thatn! = n(n − 1)(n − 2) · · · n/2 · · · 1> n(n − 1)(n − 2)...n/2> (n/2)n/21HW1 CS333Instructor: KD [email protected],2nn!<2n(n/2)n/2=2n(2k−1)n/2=2n2n(k−1)/2=12(k−1)/2=12(lg n−1)/2Observe that limn→∞1/2(lg n−1)/2= 0. From this, 2n= o(n!) and, therefore, n! = ω(2n).(b)[10 points] lg n5∈ O(n). [Hint: Refer to Example 1.27.]limn→∞lg n5n= 5 × limn→∞lg nn= 5 × limn→∞d(lg n)/dndn/dn= 5 × limn→∞1/(n ln 2)1= 0∴ lg n5∈ o(n) and lg n5∈ O(n).3: [10 points] Prove that 5n− 1 is divisible by 4 for n = 1, 2, 3, ... by induction. Divideyour proof into the three required parts: Induction Base, Induction Hypothesis, andInduction Step.[Hint: Refer to Appendix A.3.]Induction Base. If n = 1, 5n− 1 = 4, which is divisible by 4.Induction Hypothesis. Assume that 5n− 1 is divisible by 4.Induction Step.5n+1− 1 = 5 · 5n− 1 = (5n− 1) + 4 · 5n.Note that 4 · 5nis divisible by 4 and 5n− 1 is divisible by the induction hypothesis. Therefore,5n− 1 is divisible by 4 by any integer greater than or equal to 1.4: [10 points] Do Exercise 26.The outer for loop executes n times and the inner while loop executes lg n times for each executionof the for loop. Therefore, T (n) = Θ(n lg
View Full Document
Unlocking...