COT 6405 – Introduction to Theory of Algorithms Assignment 1

Description

1. Exercise 2.3-1: Using Figure 2.4 as a model, illustrate the operation of merge sort on the
array A = {3, 41, 52, 26, 38, 57, 9, 49}

2. Exercise 2.3-6: Observe that the while loop of lines 5 – 7 of the INSERTION-SORT
procedure in Section 2.1 uses a linear search to scan (backward) through the sorted
subarray A[1…j-1]. Can we use a binary search instead of a linear search to improve the
overall worst-case running time of insertion sort to Θ(𝑛lg𝑛)?

3. For the MERGE function, the sizes of the L and R arrays are one element longer
than 𝑛1 and 𝑛2, respectively. Can you rewrite the merge function with the size
of L and R exactly equal to 𝑛1 and 𝑛2?

4. Prove that 𝑒
1
𝑛 ∈ Ο(𝑛
𝑡
) (t > 0)

5. Express the function 𝑛
3
100
− 50𝑛 − 100𝑙𝑔𝑛 in terms of Θ notation.

6. Exercise 3.1-6 Prove that the running time of an algorithm is Θ(g(𝑛)) if and only
if its worst-case running time is O(g(n)) and best-case running time is Ω(𝑔(𝑛)).

7. Which is asymptotically larger: lgn or √𝑛? Please explain your reason.

8. Prove that 𝑛
𝑙𝑔𝑐 ∈ Ω(𝑐
𝑙𝑔𝑛), where c is a constant and c > 1.

9. Use the definition of limits at infinity to prove (𝑙𝑔𝑥)
𝑝 ∈ 𝑜(𝑥
𝑝
).

Definition (limits at infinity): Let 𝑓(𝑥) be a function defined on x > K for some K.

Then we say that, lim𝑥→∞
𝑓(𝑥) = 𝐿 if for every number 𝜀 > 0 there is some number
M > 0 such that | 𝑓(𝑥)– L| < 𝜀 whenever x > M