CMPSC 465 Data Structures & Algorithms
Fall 2021 and Worksheet 2
Solution
Monday, September 6,
2021
1. Growth Rate. Sort the following functions based by their growth rate. (You may assume all loga-
rithms have base 2.)
(
√
2)logn, n2, n!, (logn)!, (32)
n, log2 n, n3, log(n!), 22
n
, n
1
logn ,
log(log(n)), n2n, nlog(log(n)), 22
2n+1
, 2logn, 2
√
2logn,
√
logn
Solution:
n
1
logn < log(log(n)) < √ logn < log2 n < 2 √ 2logn < ( √ 2)logn < 2logn log(n!) < n2 < n3 < (logn)! < nlog(log(n)) < (32) n < n2n < n! < 22 n < 22 2n+1 2. Find run time. How long does the recursive multiplication algorithm (shown below) take to multiply an n-bit number by an m-bit number? Justify your answer. Algorithm 1 multiply(x,y) Input: Two n-bit integers x and y, where x,y≥ 0 Output: Their product if y = 0 then return 0 end if z = multiply(x,b y2c) if y = even then return 2z else return x+2z end if Solution: Assume we want to multiply the n-bit number x with the m-bit number y. The algorithm terminates after at most m recursive calls, because at each call y is halved so the number of digits is decreased by one. Each recursive call requires a division by 2, a parity check and a multiplication by 2; all of these takes O(1) time. There is also a sum (x+ 2z) which takes O(n) time, so the overall running time is O(m · n). 3. Computing Factorials. Consider the problem of computing N! = 1×2×·· ·×N. 1. If N is a b-bit number, how many bits long is N!, approximately (in Θ(·) form)? 2. Give a simple algorithm to compute N! and analyze its running time. CMPSC 465, Fall 2021, Worksheet 2 Solution 1 Solution: 1. When we multiply an m bit number by an n bit number, we get an O(m+n) bit number. When computing factorials, we multiply N numbers that are at most b bits long, so the final number has at most N ·b bits. In addition, if you consider the numbers from N2 to N, we multiply at least N 2 numbers that are at least b−1 bits long, so the resulting number has at least N(b−1) 2 bits. Thus, the number of bits in N! is in Θ(b ·N). More directly, we know that the number of bits of N! is Θ(log2(N!)) which we know from the previous worksheet that it is Θ(N logN) = Θ(b ·N) since b = Θ(log2 N). 2. We can compute N! naively as follows: factorial (N) f = 1 for i = 2 to N f = f · i return f Running time : we have N iterations, each one multiplying an (N ·b)-bit number (at most) by a b-bit number. Using the naive multiplication algorithm, each multiplication takes time O(N ·b2). Hence, the running time is O(N2b2). 4. Fibonacci growth. The Fibonacci numbers F0, F1, F2 . . . are defined by the recurrence F0 = 0, F1 = 1, and Fn = Fn−1 +Fn−2. In this problem we will confirm that this sequence grows exponentially fast and obtain some bounds on its growth. (a) Use induction to prove that Fn ≥ 20.5n for n≥ 6. (b) Find a constant c≤ 1 such that Fn ≥ 2cn for all n≥ 0. Show that your answer is correct. (c) What is the largest c you can find for which Fn = Ω(2cn)? Solution: (a) Base case: F6 = 8≥ 26/2 = 8. Inductive Step: For n≥ 6, we have Fn+1 = Fn +Fn−1 ≥ 2n/2 +2(n−1)/2 = 2(n−1)/2(21/2 +1)≥ 2(n−1)/22≥ 2(n+1)/2 as desired. (b)-(c) The argument above holds as long as we have, in the inductive step, 2c(n−1)(2c + 1) ≥ 2c(n+1); that is, as long as 2c ≤ (1+ √ 5)/2. CMPSC 465, Fall 2021, Worksheet 2 Solution 2