# BBM408 - Algorithm Analysis

## Assignment 1 - Due 22 March 2022

### Questions

**Question 1** Show,

a. $3n^2 - 2n = O(n^2)$

b. $3n^2 + 2000n = O(n^2)$

c. $n^2\lg n = o(n^{2+\epsilon}), \epsilon>0$

**Question 2**

Show that if merge-sort was done by dividing the array into
3 equal parts, rather than 2, the asymptotic time required
to solve it wouldn't change.

*Note:* To completely solve this problem, you need to first explain how the algorithm (esp. merge) works with 3 sub-problems (and compute the runtime of merge), and then solve the recursion.

**Question 3**

Solve the recurrence $T(n) = T(n-1) + 1/n$.

**Question 4**

Rewrite the counting sort algorithm such that the last loop iterates from the first item to the last item. Make sure that it is still a stable sorting algorithm. Demonstrate the working of your algorithm.