CMPSC 465 Data Structures & Algorithms
Fall 2021 Antonio Blanca and David Koslicki Quiz 3
Recitation Section: Date: Monday, Sep 20, 2021
Student Name: PSU Email ID:
1. (2 pts.) If T (n) = a ·T (
n
b
)+O(2n·d) for some
a> 0, b> 0 and d ≥ 0 then, we can apply the Mas-
ter Theorem and say that:
T (n) =
Θ(nd) if d > logb a
Θ(nd logn) if d = logb a
Θ(nlogb a) if d < logb a
(a) True
(b) False
Answer False.
Master Theorem applies to recurrences of the form
T (n) = a ·T (
n
b
)+O(nd)
2. (2 pts.) The recurrence relation
T (n) = 4 ·T (
n
2
)+O(n) has the solution O(n2)
(a) True
(b) False
Answer True.
Plugging in parameters into Master Theorem, we
have, a = 4, b = 2, d = 1. Thus we get O(n2)
3. (2 pts.) Given two arrays of numbers x =
[5,6,10] and y = [1,3,7]. What would be the result
of Merge(x,y) function in merge-sort algorithm?
(a) [1,3,6,5,7,10]
(b) [1,7,5,3,6,10]
(c) [1,3,5,6,7,10]
(d) [3,5,6,1,7,10]
Answer (c)
4. (2 pts.) Integer multiplication can be done in
time O(n1.59). (Note: O(log23)≈ 1.59)
(a) True
(b) False
Answer True. Shown in class.
5. (2 pts.) Suppose you are given the following two
algorithms:
• Algorithm A solves problems by dividing
them into four subproblems of half the size,
recursively solving each subproblem, and
then combining the solutions in linear time.
• Algorithm B solves problems of size n by di-
viding them into nine subproblems of size
n/3 recursively solving each subproblem,
and then combining the solutions in O(n2)
time.
Which of these algorithms has a faster running
time?
(a) A
(b) B
Answer (a) A
Algorithm A: Based on Master Theorem solves in
O(n2) time.
Algorithm B: Similarly, this runs in O(n2logn)
CMPSC 465, Fall 2021, Quiz 3 1