Algorithms Solutions - Sanjoy Dasgupta. Western Governors University AWS ML SPEC
Chapter 0– Solutions
January 30, 2007
2
0.1. a) n - 100 = Θ(n - 200)
b) n1/2 = O(n2/3)
c) 100n + log n = Θ(n + (log n)2)
d) n log n = Θ(10n log 10n)
e) log 2n = Θ(log 3n)
f) 10 log n = Θ(log(n2))
g) n1.01 = Ω(log2 n)
h) n2/ log n = Ω(n(log n)2)
i) n0.1 = Ω((log n)10)
j) (log n)log n = Ω
...[Show More]
Algorithms Solutions - Sanjoy Dasgupta. Western Governors University AWS ML SPEC
Chapter 0– Solutions
January 30, 2007
2
0.1. a) n - 100 = Θ(n - 200)
b) n1/2 = O(n2/3)
c) 100n + log n = Θ(n + (log n)2)
d) n log n = Θ(10n log 10n)
e) log 2n = Θ(log 3n)
f) 10 log n = Θ(log(n2))
g) n1.01 = Ω(log2 n)
h) n2/ log n = Ω(n(log n)2)
i) n0.1 = Ω((log n)10)
j) (log n)log n = Ω(n/ log n)
k) √n = Ω((log n)3)
l) n1/2 = O(5log2 n)
m) n2n = O(3n)
n) 2n = Θ(2n+1)
o) n! = Ω(2n)
p) (log n)log n = O(2(log2 n)2)
q) !n i=1 ik = Θ(nk+1)
0.2. By the formula for the sum of a partial geometric series, for c ̸= 1: g(n) = 1-1c-nc+1 = cnc+1 -1-1.
a) 1 > 1 - cn+1 > 1 - c. So: 1-1 c > g(n) > 1.
b) For c = 1, g(n) = 1 + 1 + · · · + 1 = n + 1.
c) cn+1 > cn+1 - 1 > cn. So: 1-c ccn > g(n) > 1-1 ccn.
0.3. a) Base case: F6 = 8 ≥ 26/2 = 8.
Inductive Step: for n ≥ 6, 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.
b-c) The argument above holds as long as we have, in the inductive step, 2c(n-1)(2c + 1) ≥ 2c(n+1),
i.e. as long as 2c ≤ 1+2√5.
0.4. a) For any 2 × 2 matrices X and Y :
XY = " x x11 21 xx12 22 # " y y11 21 y y12 22 # = " xx11 21y y11 11 ++ x x12 22y y21 21 x x11 21y y12 12 + + x x12 22y y22 22 #
This shows that every entry of XY is the addition of two products of the entries of the original
matrices. Hence every entry can be computed in 2 multiplications and one addition. The whole
matrix can be calculated in 4 multiplications and 4 additions.
b) First, consider the case where n = 2k for some positive integer k. To compute, X2k, we can
recursively compute Y = X2k-1 and then square Y to have Y 2 = X2k Unfolding the recursion,
this can be seen as repeatedly squaring X to obtain X2, X4, · · · , X2k = Xn. At every squaring,
we are doubling the exponent of X, so that it must take k = log n matrix multiplications to
produce Xn. This method can be easily generalized to numbers that are not powers of 2, using
the following recursion:
Xn = $ X(·X(X⌊n/ ⌊n/ 2⌋) 22⌋)2 if if nn is even is odd
The algorithm still requires O(log n) matrix multiplications, of which log n are squares and at
most log n are multiplications by X.
[Show Less]