CMPSC 465 Data Structures & Algorithms
Fall 2021 and HW 1
1. (5 pts.) Problem 1
I understand the course policies.
2. (36 pts.) Problem 2
(a) f = O(g): limn→∞
6n·2n+n100
3n = limn→∞
6n
1.5n + limn→∞
n100
3n = 0, now since limn→∞
f (n)
g(n) = 0, we have
f = O(g).
(b) f = Θ(g): limn→∞
log2n
log3n = limn→∞
log2+logn
log3+logn = 1.
(c) f = Ω(g): limn→∞
√
n
3√n = ∞
(d) f = Ω(g): limn→∞
n2
logn
n(logn)4 = limn→∞
n
(logn)5 = ∞
(e) f = Θ(g): n2 dominates both n logn, and (logn)5 terms, which implies that f = Θ(n2),g = Θ(n2),
(f) f = Ω(g): Let k = b
√
nc, then we have f (k) = 8k
2
· k4, g(k) = k!. Now, note that 8k ≥ k for all k ≥ 1,
and so 8k
2
= (8k)k ≥ kk for all k ≥ 1. From Worksheet 1, we know that kk ≥ k! and so 8k
2
≥ k! which
also implies that 8k
2
·k4 ≥ k! for all k≥ 1. Thus, it follows from the definition of O that k! = O(8k
2
·k4)
(taking c = 1 and n0 = 1); it follows from the definition of Omega that f = Ω(g).
(g) f = Θ(g): we can write 8 logn = log(n8) < log(n9 + logn) < log(n10) = 10logn⇒ f = Θ(log2n).
Also, g = log2n = log2+ logn = Θ(logn).
(h) f =O(g): For function f we have f =(log2 n)
log2 n = 2(log2 log2 n)(log2 n). Then, we can write limn→∞
g(n)
f (n) =
limn→∞
2(log2 n)
2
2(log2 log2 n)(log2 n)
= limn→∞ 2(log2 n)
2−(log2 log2 n)(log2 n). Now note that limn→∞
(log2 n)
2
(log2 log2 n)(log2 n)
=
limn→∞
log2 n
log2 log2 n
= ∞, which also means that limn→∞(log2 n)
2 − (log2 log2 n)(log2 n) = ∞, therefore
we have limn→∞
g
f = ∞, this implies f = O(g).
(i) f =Θ(g): We can write f = n log(n20) = 20n logn=Θ(n logn), and g= log(3n!) =Θ(log(n!)). Thus,
it remains to show that log(n!) =Θ(n logn), but we know this is true, as we saw the proof in Worksheet
1, problem 2(i).
3. (15 pts.) Problem 3
By the formula for the sum of a partial geometric series, for c 6= 1: S(k) :=
k
∑
i=0
ci = 1−c
k+1
1−c . Thus,
• If c > 1, we have ck+1 > 1, and then S(k) = c
k+1−1
c−1 . Now we can write limk→∞
S(k)
ck
= limk→∞
c− 1
ck
c−1 =
c
c−1 −
1
c−1 limk→∞
1
ck
. Since c > 1, we can conclude limk→∞
1
ck
= 0. Therefore we have limk→∞
S(k)
ck
=
c
c−1 . Note that 0 <
c
c−1 < ∞, therefore S(k) = Θ(c
k)
• If c = 1, then every term in the sum is 1. Thus, S(k) = k+1 = Θ(k).
• If c < 1, then 11−c >
1−ck+1
1−c = S(k)> 1. Thus, S(k) = Θ(1).
4. (20 pts.) Problem 4
CMPSC 465, Fall 2021, HW 1 1
(a) f (n) is a degree d polynomial. We have limn→∞
f (n)
nk
= 0, for k > d. So, we can conclude that for k≥ d,
f (n) = O(nk). On the other hand, for k < d, limn→∞
f (n)
nk
= ∞, which means that f (n) = Ω(nk) in this
case. Also for k = d, we have limn→∞
f (n)
nk
= ad , so f (n) = Θ(nk)
(b) Part (b) is a special case of part (c); same proof works. Alternatively, this problem can also be solved
by remembering that ∑nk=1 k
2 =
n(n+1)(2n+1)
6 .
(c) Since k ≤ n every term in the sum is at most n, so
n
∑
k=1
k j = 1 j + · · ·+n j ≤ n j + · · ·+n j =
n
∑
k=1
n j = n j+1.
We do something similar for the lower bound. The only additional idea is that we only look at the
second half of the sum. The smallest element in the second half of the sum correspond to k = n/2
(assuming without loss of generality that n is even). Then,
n
∑
k=1
k j ≥
n
∑
k=n/2
k j ≥
n
∑
k=n/2
(n/2) j = 2− j−1n j+1.
(d) First we show the upper bound. ∑ni=1 ∑
n
j 6=i, j=1
i j ≤ (∑ni=1 i)
2 = (
n(n+1)
2 )
2 = O(n4). For the lower bound,
note that we can write: ∑ni=1 ∑
n
j 6=i, j=1
i j ≥ ∑ni= n2 ∑
n
j 6=i, j= n2
i j ≥
(n
2
)
(n2)
2 =
n(n−1)
2
n2
4 = Ω(n
4)
5. (24 pts.) Prove the statements
1. Based on the definition, f (n) = O(g(n)) means that there exist positive constants c and n0 such that
0 ≤ f (n) ≤ cg(n) for all n ≥ n0. Thus, 0 ≤ 1c f (n) ≤ g(n) for all n ≥ n0. As
1
c is positive, given the
definition of the Ω-notation, we can deduce that f (n) = O(g(n)) means the same as g(n) = Ω( f (n)).
2. According to the definition of Θ-notation, we need to find two constants c1 and c2 such that 0 ≤
c1( f (n)+ g(n)) ≤ max( f (n),g(n)) ≤ c2( f (n)+ g(n)) for all n ≥ n0 where n0 is a positive constant.
Given that f (n) and g(n) are asymptotically non-negative, we can make the following conclusions:
• max( f (n),g(n))≤ f (n)+g(n)
• max( f (n),g(n)) comprises at least half of f (n)+ g(n), meaning max( f (n),g(n)) ≥ 0.5( f (n)+
g(n))
• 0.5( f (n)+g(n))≥ 0
As such, c1 could be 0.5 and c2 could be 1. Therefore, max( f (n),g(n)) = Θ( f (n)+g(n)).
3. We know that one can directly translate between logarithms of different bases using the following
fundamental identity:
loga n =
logb n
logb a
So we can get loga n =
1
logb a
logb n≤ c logb n, we can say that loga n = Θ(logb n)
CMPSC 465, Fall 2021, HW 1 2
Rubric:
Problem 1
Assign full credit if “I understand the course policies” is written. Subtract one point if they forgot to mention
their collaborators or write “none” for the collaborators.
Problem 2
Each part is 4 pts: 2 pt for identifying right relation between f and g and 2 pts for a reasonable explanation.
Problem 3
Case c > 1: 6 pts
Case c = 1: 3 pts
Case c < 1: 6 pts
Problem 4
Each part is worth 5 pts.
part a: showing only one case is worth 2.5 pts.
part b-c-d: showing only upper bound is worth 2 pts, and showing only lower bound is worth 3 pts.
Problem 5
1. This part is worth 8 points.
5 points: the inference from 0≤ f (n)≤ cg(n) to 0≤ 1c f (n)≤ g(n)
3 points: emphasize 1c is positive
2. This part is worth 8 points.
3 points: correctly prove the upper bound
4 points: correctly prove the lower bound
1 point: emphasize the lower bound i.e. c1( f (n)+g(n)) is non-negative
3. This part worth 8 points, students should get 4 point if they show loga n =
logb n
logb a
, and get the rest 4
point if they show loga n =
1
logb a
logb n≤ c logb n
CMPSC 465, Fall 2021, HW 1 3