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.

Answers

Question 1

a.

$$3n^2 - 2n = O(n^2)\\ 3n^2 - 2n \leq cn^2\\ -2 \leq (c-3)n\\ \frac{-2}{c-3} \leq n\\$$

this holds for $c=4$ and $n_0=1$. Note that, for $c < 3$, the inequality must be reversed. Hence, we choose 4.

b.

$$3n^2 + 2000n = O(n^2)\\ 3n^2 + 2000n \leq cn^2\\ 2000 \leq (c-3)n\\ \frac{2000}{c-3} \leq n\\$$

this holds for $c=4$ and $n_0=2000$

c.

$$n^2\lg n = o(n^{2+\epsilon}) \\ n^2\lg n < cn^{2+\epsilon}\\ \lg n < cn^\epsilon\\ \frac{\lg n}{n^\epsilon} < c\\$$

now,

$$\lim_{n->\inf}{\frac{\lg n}{n^\epsilon}} =\lim_{n->\inf}{\frac{1/n}{\epsilon n^{\epsilon-1}}} =\lim_{n->\inf}{\frac{1}{\epsilon n^\epsilon}=0}$$

So, for sufficiently large $n$, $\frac{\lg n}{n^\epsilon} < c$, for any $c>0$.

Question 2

In 3-part merge, we create 3 sub arrays for each part just like in the Algorithm MERGE in the book ( the algorithm in the book works with 2 parts). We then go from the first element to the last element, but this time we compare the subarray head elements and choose the minimum. This only adds one more comparison to each element and doesn't change the asymptotic runtime of MERGE.

Recursion:

$$T(n) = 3T(n/3) + \Theta(n)$$

Apply, master method with a=3, b=3, f(n)=cn:

Case 1: cn is NOT $O(n^{\log_3 3-\epsilon})$

Case 2: $cn = \Theta(n^{\log_3 3} \lg^k n)$ for $k=0$, hence T(n) is $\Theta(n\lg n)$.

Case 3: No need to check.

Question 3

$T(n) = T(n-1) + 1/n$

Master method does not apply, because a=1 and b=1. $\log_1 1$ is not defined. We try recursion tree:

1/n
 |
1/(n-1)
 |
1/(n-2)
 | 
...
 | 
1/1

The sum is $\frac{1}{1} + \frac{1}{2} + \frac{1}{3} + ... + \frac{1}{n-1} + \frac{1}{n} = \ln n+\gamma$ where $\gamma$ is the Euler-Mascheroni constant. Hence, $T(n)=\Theta(\log n)$.

Question 4

COUNTING-SORT(A, B, k):
 1 let C[0..k] be a new array
 2 for i = 0 to k
 3    C[i] = 0
 4 for j = 1 to A.length
 5    C[A[j]] = C[A[j]] + 1
 6 // C[i] now contains the number of elements equal to i.
 7 C[k] = A.length + 1 - C[k]
 7 for i = k-1 to 1
 8    C[i] = C[i+1] - C[i]
 9 // C[i] now contains where in list B, the sequence of i's start
10 for j = 1 to A.length
11    B[C[A[j]]] = A[j]   
12    C[A[j]] = C[A[j]] + 1

After first loop,
          1 2 3 4 5 6 7 8 9 10         1 2 3 4 5 6 7 8 9 10         1 2 3 4 
    A -> |3|4|1|1|3|2|4|1|1|3|   B -> | | | | | | | | | | |   C -> |0|0|0|0|
After second loop,
          1 2 3 4 5 6 7 8 9 10         1 2 3 4 5 6 7 8 9 10         1 2 3 4 
    A -> |3|4|1|1|3|2|4|1|1|3|   B -> | | | | | | | | | | |   C -> |4|1|3|2|
After third loop,
          1 2 3 4 5 6 7 8 9 10         1 2 3 4 5 6 7 8 9 10         1 2 3 4 
    A -> |3|4|1|1|3|2|4|1|1|3|   B -> | | | | | | | | | | |   C -> |1|5|6|9|
Within fourth loop,
          1 2 3 4 5 6 7 8 9 10         1 2 3 4 5 6 7 8 9 10         1 2 3 4 
    A -> |3|4|1|1|3|2|4|1|1|3|   B -> | | | | | |3| | | | |   C -> |1|5|7|9|
    A -> |3|4|1|1|3|2|4|1|1|3|   B -> | | | | | |3| | |4| |   C -> |1|5|7|10|
    A -> |3|4|1|1|3|2|4|1|1|3|   B -> |1| | | | |3| | |4| |   C -> |2|5|7|10|
    A -> |3|4|1|1|3|2|4|1|1|3|   B -> |1|1| | | |3| | |4| |   C -> |3|5|7|10|
    A -> |3|4|1|1|3|2|4|1|1|3|   B -> |1|1| | | |3|3| |4| |   C -> |3|5|8|10|
    A -> |3|4|1|1|3|2|4|1|1|3|   B -> |1|1| | |2|3|3| |4| |   C -> |3|6|8|10|
    A -> |3|4|1|1|3|2|4|1|1|3|   B -> |1|1| | |2|3|3| |4|4|   C -> |3|6|8|11|
    A -> |3|4|1|1|3|2|4|1|1|3|   B -> |1|1|1| |2|3|3| |4|4|   C -> |4|6|8|11|
    A -> |3|4|1|1|3|2|4|1|1|3|   B -> |1|1|1|1|2|3|3| |4|4|   C -> |5|6|8|11|
    A -> |3|4|1|1|3|2|4|1|1|3|   B -> |1|1|1|1|2|3|3|3|4|4|   C -> |5|6|9|11|

Items with equal values are processed in the same order as they are given in the input array, and an item is never placed before an existing item with the same value. Therefore this is still a stable sort.