CS计算机代考程序代写 data structure algorithm CMPSC 465 Data Structures & Algorithms

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