## Description

Assignment 1 (10 points for each question)

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