BBM408 - Algorithm Analysis

Assignment 1 - Due 22 March 2022

Questions

Question 1 Show,

a. 3n2−2n=O(n2)3n^2 - 2n = O(n^2)
b. 3n2+2000n=O(n2)3n^2 + 2000n = O(n^2)
c. n2lg⁡n=o(n2+ϵ),ϵ>0n^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/nT(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.