EECE 340 Homework 4 Solution, Spring 2016

CMPS 211 Assignment 3 - Solution Section 3.2 2 - a) f(x) = 17x + 11; yes C = 1, k = 11 c) f(x) = xlogx; yes C = 1 k = 1 d) f(x) = x4=2; no e) f(x) = 2x; no 8- b) f(x) = 3x5 + (log x) 4 3x5 ≤ 3x5 for x > 1 log x < x for x > 1 ⇒ 3x5 + (log x) 4 < 3x5 + (x)4 = 3x5 + x4 < 3x5 + x5 = 4x5 ⇒ f(x) = Ο (x 5 ) for c = 4 and x > 1 c) f(x) = 1 1 4 2 4 + + + x x x x4 + x2 + 1 ≤ x4 + x4 + x4 = 3 x4 for x > 1 x4 + 1 ≥ x -4 for x > 1 ⇒ 1 1 4 + x ≤ x4 for x > 1 ⇒ 1 1 4 2 4 + + + x x x ≤ 4 3 4 x x = 3 ⇒ f(x) = Ο (x 0 ) = Ο (1 ) for c = 3 and x > 1 14- a) Is x3 = Ο (x2) ? NO Want to show that there doesn’t exist a pair of c and k to satisfy the equation x3 ≤ c x2 and x > k Since x is positive, we can divide both sides of the inequality by x, then x2 ≤ c x and x > k but there are no values of c and k to satisfy this inequality, if we set k = 1. ⇒ x3 ≠ Ο (x2). d) Is x3 = Ο (x2 + x4) ? YES x3 ≤ x4 for x > 1 ⇒ x3 ≤ x4 + x2 for x > 1 since x2 > 0 ⇒ x3 ≤ x4 + x4 = 2 x4 for x > 1 since x2 ≤ x4 ⇒ x3 = Ο (x2 + x4) for c = 2 and x > 1 f) Is x3 = Ο (x3 / 2) ? YES x3 ≤ x3 = 2 (x3 / 2) for x > 1 ⇒ x3 ≤ 2 (x3 / 2) for x > 1 ⇒ x3 = Ο (x3 / 2) for c = 2 and x > 1 18- Show that 1k + 2k + … + nk = Ο (n k+1 ) 1k ≤ nk for n ≥ 1 2k ≤ nk for n ≥ 1 M nk ≤ nk for n ≥ 1 ⇒ 1k + 2k + … + nk ≤ nk + nk + … + nk (n times) ⇒ 1k + 2k + … + nk ≤ n ( nk ) = nk+1 ⇒ 1k + 2k + … + nk = Ο (n k+1 ) for c = 1, n ≥ 1 and k > 0 24- a) Show 3x + 7 = Θ (x). 1. 3x + 7 ≤ 4x since 7 ≤ x for x > 7 ⇒ 3x + 7 = Ο (x) for x > 7 2. x ≤ 3x + 7 since x is positive ⇒ x = Ο (3x + 7) for x > 0 ∴ 3x + 7 = Θ (x) for x > 7. c) Show x + 1/2 = Θ (x). 1. x + 1/2 ≤ x + 1 ⇒ x + 1/2 = Ο (x) for x > 1 2. x-1 ≤ x + 1/2 since x-1 ≤ x + 1/2 ≤ x +1 ⇒ x = Ο (x + 1/2) for x > 1 ∴ x + 1/2 = Θ (x) for x > 1. e) Show log10 x = Θ (log2 x). 1. log10 x = log10 log x = Ο (log x) for x > 1 2. log2 x = log 2 log x = Ο (log x) for x > 1 ∴ log10 x = Θ (log2 x) for x > 1. Section 3.3 4- To find k x 2 by successive squaring requires k+1 multiplications. To find k x 2 by multiplying x by itself requires 2k multiplications. The first approach is naturally more efficient. 8- a) Evaluating 1 3 2 x + x + at x = 2: Input: c = 2, a0 = 1, a1 = 1, a2 = 3. 0. y = 3 initialization of y 1. i = 1, y = 3⋅2 + 1 = 7 first iteration in for loop 2. i = 2, y = 7⋅2 + 1 = 15 second iteration in for loop Final Answer: y = 15 b) In each iteration of the for loop, one multiplication and one addition are used, so the total number of multiplications and additions in the algorithm is n multiplications and n additions. 12- a) To find the maximum of a sequence of n integers: always requires n-1 comparisons; traverse list from 2 to n, comparing at each iteration b) To locate an element in a list of n terms with linear search: Least number of comparisons is 1; occurs if the element to be located is the first element in the list c) To locate an element in a list of n terms with binary search: Least number of comparisons is 1; occurs if the element to be located is the first element inspected, i.e. the middle element in the list 16- The search algorithm resembles binary search, except that it divides the list of numbers into 4 sublists. Since binary search has worst-case time complexity of O(log n) where log n = log2 n, then this search algorithm will worst-case time complexity of O(log4 n) = O(log n). This is caused by the fact that the list is continuously subdivided into 4 equal-sized sublists.