CMPSC 465 Data Structures & Algorithms
Fall 2021 and HW 2
1. (20 pts.) Problem 1
(a) This is false. A counterexample is f (n) = 2n and g(n) = n. f (n) is O(g(n)) in this case because
we can find constants c = 3 and n0 = 1 such that 0 ≤ f (n) ≤ cg(n) for all n ≥ n0. However, since
2 f (n) = 22n and 2g(n) = 2n, limn→∞
22n
2n = ∞ 6= 0. So, 2
f (n) grows faster than 2g(n) asymptotically. Thus,
the statement is false.
(b) This is true. Proof: As f (n) is O(g(n)), there exist positive constants c and n0 such that 0 ≤ f (n) ≤
cg(n) for all n≥ n0. Then, 02≤ f (n)2≤ c2g(n)2 for all n≥ n0. Let d = c2. We have 0≤ f (n)2≤ dg(n)
2
for all n≥ n0. So, we’ve found constants d and n0 that satisfy the definition of Big-O notation. Thus,
f (n)2 is O(g(n)2).
(c) This is false. A counterexample is f (n) = 2n and g(n) = n. f (n) is O(g(n)) in this case because we
can find constants c = 3 and n0 = 1 such that 0≤ f (n)≤ cg(n) for all n≥ n0. Let h(n) be 0.5n. h(n)
is O(g(n)) in this case because we can find constants c = 3 and n0 = 1 such that 0 ≤ h(n) ≤ cg(n)
for all n ≥ n0. However, since 2 f (n) = 22n and 2h(n) = 20.5n, limn→∞ 2
2n
20.5n = ∞ 6= 0. So, 2
f (n) grows
asymptotically faster than 2h(n), which is an example of 2O(g(n)). Thus, the statement is false.
(d) This is false. A counterexample is f (n) = 2 and g(n) = 1. f (n) is O(g(n)) in this case because we can
find constants c = 3 and n0 = 1 such that 0≤ f (n)≤ cg(n) for all n≥ n0. However, log2 f (n) = 1 and
log2 g(n) = 0. As a result, no positive constants c and n0 can satisfy that 0 ≤ log2 f (n) ≤ c log2 g(n)
for all n ≥ n0 because log2 f (n) > c log2 g(n) = 0 no matter which value c takes. So, the statement is
false.
(e) This is false. A counterexample is f (n) = 0.5 and g(n) = 1. log2 f (n) is O(log2 g(n)) in this case
because we can find constants c = 1 and n0 = 1 such that 0 ≤ f (n) ≤ cg(n) for all n ≥ n0. However,
log2 f (n) =−1. As a result, f (n) log2 f (n) =−0.5, and 0≤ f (n) log2 f (n) can never be satisfied. So,
the statement is false.
2. (20 pts.) Problem 2
(a) We can observe that the turn i with the coefficient ai has log2 i multiplications. Overall, there are
n
∑
i=1
log2 i= log2(n!) multiplications, thus O(n logn) (from worksheet 1 problem 2-i, log(n!)=Θ(n logn)).
There are n additions, thus O(n).
(b) If we consider the value of z after each iteration we obtain
i = n−1 → z = anx0 +an−1
i = n−2 → z = anx20 +an−1×0 +an−2
i = n−3 → z = anx30 +an−1x
2
0 +an−2×0 +an−3
. . .
i = 0 → z = anxn0 +an−1x
n−1
0 + · · ·+a1x0 +a0,
To describe in more detail, since the coefficients ai are added to z in order from n to 0, the term with
coefficient ai multiplies with x0 a total of i times. So, we have the desired polynomial a0 + a1x0 +
a2x20 + · · ·+anx
n
0 at the end.
CMPSC 465, Fall 2021, HW 2 1
(c) Every iteration of the for loop uses one multiplication and one addition, so the routine uses n additions
and n multiplications.
3. (20 pts.) Problem 3
Let M(n,m) be the time it takes to multiply a n bit number by a m bit number. The while loop in algorithm 2
takes y−1 iterations, and in each iteration we have to compute z ·x. Note that the multiplication of an n1 bit
number by an n2 bit number results in a number with at most n1 +n2 bits. Therefore, at ith iteration of while
loop, z has O(in) number of bits (before multiplication), therefore the cost of multiplication at ith iteration
is O(M(ni,n)), and since there are y−1 iterations, the total running time would be:
y−1
∑
i=1
O(M(ni,n)) (1)
(a) For this part, note that M(ni,n) = O(n2i). As a result we have:
y−1
∑
i=1
O(M(ni,n)) =
y−1
∑
i=1
O(in2) = O(n2)
y−1
∑
i=1
i = O(n2)
(y−1)y
2
= O(n2y2) (2)
(b) For this part, note that M(ni,n) = O(ni log(ni)), since ni > n. Therefore we have:
y−1
∑
i=1
O(M(ni,n)) =
y−1
∑
i=1
O(ni log(in)) (3)
= O(n)
y−1
∑
i=1
i log(in) (4)
= O(n logn)
y−1
∑
i=1
i+O(n)
y−1
∑
i=1
i log i (5)
= O(y2n logn)+O(ny2 logy) (6)
= O(n2y2) (7)
Note: This problem turned out to be harder than we anticipated, so everyone will get the maximum
score (10 pts).
4. (20 pts.) Problem 4
(a) For any 2×2 matrices X and Y :
XY =
(
x11 x12
x21 x22
)(
y11 y12
y21 y22
)
=
(
x11y11 + x12y21 x11y12 + x12y22
x21y11 + x22y21 x21y12 + x22y22
)
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 8 multiplications and 4 additions.
(b) Let A′ = XA, where A is an arbitrary 2×2 matrix, and X =
(
0 1
1 1
)
. Since entries of A′ are only the
sum of at most two entries of A, then we can say that number of bits of A′ entries are at most one bit
more than number of bits in A. Therefore, each time we multiply a matrix by X , the number of bits of
each entry only increased by at most one bit, so we can conclude that X i has as most i bits, which is
O(n), since i < n.
CMPSC 465, Fall 2021, HW 2 2
(c) In each call of matrix(X ,n), we will go from n to n2 . So, it takes blog2 nc recursive calls for the
algorithm to end, and to return the output. Also, in each call, we have to do either Z ·Z or Z ·Z ·X .
Now, note that in ith iteration or ith recursive call we have Z = X
n
2i , which means that entries of Z at
ith recursive call has at most n2i bits (According to part b). Now note that for computing either Z ·Z or
Z ·Z ·X , we have constant number of multiplication, and additions between numbers with at most n2i
bits, which takes O(M( n2i ))< O(M(n)) time. Therefore, the total run time can be written as follows:
blog2 nc
∑
i=1
O(M(
n
2i
)) = O(M(n) logn) (8)
5. (20 pts.) Problem 5
(a) The answer is at least 2h and at most 2h+1−1. This is because a complete binary tree of height h−1
has ∑h−1i=0 2
i = 2h−1 elements, and the number of elements in a heap of depth h is strictly larger than
the number of vertices in a complete binary tree of height h−1 and less than (or equal) the number of
nodes in a complete binary tree of height h.
(b) The array is not a Min heap. The node containing 26 is at position 9 of the array, so its parent is at
position 4, which contains 35. This violates the Property.
(c) Consider the min heap with n vertices where the root and every other node contains the number 2.
Suppose now that 1 is inserted to the first available position at the lowest level of the heap. That is,
A[i] = 2 for 0≤ i≤ n−1 and A[n] = 1. Since 1 is the minimum element of the heap, when Heapify-UP
is called from position n, the node containing 1 must be swapped through each level of the heap until
it is the new root node. Since the heap has height blognc, Heapify-UP has worst-case time Ω(logn).
(d) Recall that heapsort works by first building a Min heap. It then uses the Min heap to produce a sorted
array by repeatedly swapping the root with the last element and calling Heapify-Down from the root.
If the array is already sorted in increasing order, then Build-Heap will call Heapify-Down O(n) times
but no swaps will occur. Hence, Build-Heap would take O(n) time in this case. (Recall that in lectures
we showed that Build-Heap would take O(n logn), but it was also mentioned that in fact Build-Heap
takes O(n) in the worst case.) However, heapsort will still take O(n logn). This is because each time
we swap the root of the heap with the last element, we have to call Heapify-Down which will make
O(logn) swaps.
If the array is sorted in decreasing order, it can also be similarly checked that mergesort will also take
Θ(n logn) time. Build-Heap takes O(n), but Heapify-Down is called O(n) times.
CMPSC 465, Fall 2021, HW 2 3
Rubric:
Problem 1, total points 20
(a) 4 points.
1 point: correct conclusion (statement is false)
1.5 points: a counterexample that makes sense
1.5 points: an explanation on why the provided counterexample shows the statement is false
(b) 4 points.
1 point: correct conclusion (statement is true)
3 points: a proof that reasons by making an association with the definition of big-O notation
(c) 4 points.
1 point: correct conclusion (statement is true)
3 points: a proof that reasons by making an association with the definition of big-O notation
(d) 4 points.
1 point: correct conclusion (statement is true)
1 point: make an association with the definition of big-O for f (n) and g(n) in proof
1 point: make an association with the definition of big-O for g(n) and O(g(n)) in proof
1 point: how the proof reaches to the conclusion makes sense
(e) 4 points.
1 point: correct conclusion (statement is false)
1.5 points: a counterexample that makes sense
1.5 points: an explanation on why the provided counterexample shows the statement is false
Problem 2, total points 20
(a) 5 points.
1.5 points: correct answer for the number of sums
1.5 points: correct answer for the number of multiplications
2 points: the explanations make sense
Note: answers with exact numbers only or in big-O notations only are both acceptable, as long as the
provided exact numbers or the big-O notations are correct.
(b) 10 points.
3 points: provide a proof
7 points: describe the pattern of the loop in the proof
(c) 5 points.
1.5 points: correct answer for the number of sums
1.5 points: correct answer for the number of multiplications
2 points: the explanations make sense
Note: answers with exact numbers only or in big-O notations only are both acceptable, as long as the
provided exact numbers or the big-O notations are correct.
Problem 3, 20 pts
(a) part a is worth 10 pts. 6 pts for showing the runtime for each iteration of while loop (note that the ith
iteration of algorithm 2 takes O(i ·n2)), and 4 pts for showing the total runtime of algorithm (the total
runtime is O(n2y2)).
CMPSC 465, Fall 2021, HW 2 4
(b) part b is worth 10 pts. Assign 10 pts to every student.
Problem 4, 20 pts
(a) part a is worth 3 pts. Computing the multiplication of two matrices correctly is worth 2 pts, even if the
final answer is not correct.
(b) part b is worth 5 pts.
(c) part c is worth 12 pts. 3 pts, for showing that there are O(log2 n) recursive call, and 9 pts for showing
the runtime for each recursive call which is O(M( n2i )). However, O(M(n)) is also accepted for the
runtime of each recursive call.
Problem 5, 20 pts.
(a) 5 points for this part, if at least 2h is pointed, 1.5 pts, if at most 2h+1−1 is pointed, 1.5 pts, reasonable
explanation 2 pts
(b) answer as No, 2.5 pts, denote that element 26 is in the wrong place, and it should be swapped with 35,
2.5 pts
(c) any clear and reasonable explanation should be 5 pts
(d) increasing order, running time is O(n logn) , 1 pts, reasonable explanation 1.5 pts, decreasing order,
running time is O(n logn), 1 pts, reasonable explanation 1.5 pts
CMPSC 465, Fall 2021, HW 2 5