CMPSC 465 Data Structures & Algorithms
Fall 2021 and Worksheet 1
Monday, Aug 30, 2021
1. Compare Growth Rates. Order the following functions by asymptotic growth:
(i) f1(n) = 3n
(ii) f2(n) = n
1
3
(iii) f3(n) = 12
(iv) f4(n) = 2log2 n
(v) f5(n) =
√
n
(vi) f6(n) = 2n
(vii) f7(n) = log2 n
(viii) f8(n) = 2
√
n
(ix) f9(n) = n3
Solution f3, f7, f2, f5, f4, f9, f8, f6, f1
2. Prove Order of Growth. Prove the following:
(i) log(n!) = Θ(n logn)
(ii) ∑ni=1
1
i = Θ(logn)
Solution
(i) Observe that
n! = 1∗2∗3 · · · ∗n≤ n∗n∗n · · · ∗n≤ nn
and assuming n is even (without loss of generality)
n! = 1∗2∗3 · · · ∗n≥ n∗ (n−1)∗ (n−2) · · · ∗ (n−n/2)≥
(n
2
) n
2+1
.
Hence
(
n
2
) n
2 ≤ n!≤ nn. Then,
n
2
log
(n
2
)
≤ log(n!)≤ n logn.
(ii) The main idea for both upper and lower bound is that for any k there exist i such that 12i+1 ≤
1
k ≤
1
2i . Note that for several k’s the value of i is the same, so we can replace several 1/k’s by the
same inverse power of 2 to obtain a more manageable sum.
CMPSC 465, Fall 2021, Worksheet 1 1
More precisely, for the upper bound we replace each 1/k with 1/2i, where 2i is the largest power
of 2 smaller than or equal to k. For simplicity assume n is a power of 2, i.e. n = 2` for some
` ∈ N. (Note that this assumption has no effect on the order of the sum.) Therefore,
n
∑
k=1
1
k
= 1+
1
2
+
1
3
+ · · ·+
1
n
≤ 1+
1
2
+
1
2
+
1
4
+
1
4
+
1
4
+
1
4
+
1
8
+ · · ·
≤ 1+
3
∑
k=2
1
2 +
7
∑
k=4
1
4 + · · ·+
n
∑
k=n/2
1
n/2
= 1+2 12 +4
1
4 + · · ·+2
`−1 1
2`−1
= `= O(logn).
We can do the same for the lower bound, except we replace 1/k with 1/2i, where 2i is the
smallest power of 2 larger than k.
Note. This problem can also be solved by integrating: ∑nk=1
1
k =
∫ n+1
1
⌈
1
x
⌉
dx = Θ(logn).
3. Analyze Running Time. For each pseudo-code below, give the asymptotic running time in Θ
notation.
(i)
for i := 1 to n do
j := i;
while j < n do
j := j+5;
end
end
Solution For any fixed i, the inner loop performs Θ(n− i) steps. The running time is then
n
∑
i=1
Θ(n− i) =
n−1
∑
i=0
Θ(i) = Θ(n2).
(ii)
for i := 1 to n do
for j := 4i to n do
s := s+2;
end
end
Solution For any fixed i≤ n/4, the inner loop iterates n−4i times, and one time when i > n/4.
Then, the running time is
3n
4
+
n/4
∑
i=1
(n−4i) = Θ(n2).
(iii)
for i := 1 to n do
j := 2;
while j < i do
j := j4;
end
end
CMPSC 465, Fall 2021, Worksheet 1 2
Solution For each fixed i, the inner loop iterates Θ(log log i) times, since the value of j in the
k-th iteration of the inner loop is 24
k
, and it runs until 24
k
≤ i. Hence, the running time is
∑
n
i=1 Θ(log log i) = Θ(n log logn).
CMPSC 465, Fall 2021, Worksheet 1 3