CMPSC 465 Data Structures & Algorithms
Fall 2021 and HW 1
Due September 7, 10:00 pm
Instructions: You are encouraged to solve the problem sets on your own, or in groups of three to five
people, but you must write your solutions strictly by yourself. You must explicitly acknowledge in your
write-up all your collaborators, as well as any books, papers, web pages, etc. you got ideas from.
Formatting: Each part of each problem should begin on a new page. For this homework, we will make an
exception with Problem 2 since it consists of multiple short parts; therefore, use a single page for Problem
2. So, you should use 1 page for problem 1, 1 pages for problem 2, 1 page for problem 3, 4 for problem 4
(one for each part) and 3 for problem 5. Each page should be clearly labeled with the problem number and
the problem part. The pages of your homework submissions must be in order. You risk receiving no credit
for it if you do not adhere to these guidelines.
Late homework will not be accepted. Please, do not ask for extensions since we will provide solutions
shortly after the due date. Remember that we will drop your lowest two scores.
This homework is due Tuesday, September 7, at 10:00 pm electronically. You need to submit it via Grade-
scope (Class code 6PERPR). Please ask on Piazza about any details concerning Gradescope and formatting.
1. (5 pts.) Getting started
Please read the course policies on the syllabus, especially the course policies on collaboration. If you have
any questions, contact the instructors. Once you have done this, please write “I understand the course
policies.” on your homework to get credit for this problem.
2. (36 pts.) Comparing growth rates. In each of the following situations, indicate whether f = O(g), or
f = Ω(g), or both (in which case f = Θ(g)). Give a one sentence justification for each of your answers.
f (n) g(n)
a) 6n ·2n +n100 3n
b) log(2n) log(3n)
c)
√
n 3
√
n
d) n
2
logn n(logn)
4
e) n logn+n2 10n2 +(logn)5
f) 8n ·n2 (b
√
nc)!
g) log(n9 + logn) log(2n)
h) (log2 n)
log2 n 2(log2 n)
2
i) n log(n20) log(3n!)
CMPSC 465, Fall 2021, HW 1 1
3. (15 pts.) Geometric progressions growth
Prove the following:
k
∑
i=0
ci =
Θ(ck) if c > 1,
Θ(k) if c = 1,
Θ(1) if 0 < c < 1.
4. (20 pts.) Useful identities.
Show the following statements hold:
(a) Let f (n) = ∑di=0 ai ·n
i with ad 6= 0. Show that: f (n) =
O(nk) if k ≥ d,
Ω(nk) if k ≤ d,
Θ(nk) if k = d.
(b) ∑nk=1 k
2 = Θ(n3).
(c) ∑nk=1 k
j = Θ(n j+1) for any constant j > 0.
(d)
n
∑
i=1
n
∑
j=1, j 6=i
i j = Θ(n4).
5. (24 pts.) Practice with the definitions
(a) Prove that f (n) = O(g(n)) if and only if g(n) = Ω( f (n)).
(b) Let f (n) and g(n) be asymptotically non-negative functions. Using the basic definition of Θ, prove
that max( f (n),g(n)) = Θ( f (n)+g(n)).
(c) Using the basic definition of Θ, prove that loga n = Θ(logb n) for all a,b > 1.
CMPSC 465, Fall 2021, HW 1 2