3.1 O-notation, $\Omega$-notation, and $\Theta$-notation

3.1-1

Modify the lower-bound argument for insertion sort to handle input sizes that are not necessarily a multiple of 3.

At least $\lfloor \frac n 3 \rfloor \geq \frac 3n-1$ elements have to pass through at least $\lfloor \frac n 3 \rfloor \geq \frac 3n-1$ the time taken by INSERTION-SORT in the worst case is at least proportional to $(\frac 3n-1)(\frac 3n-1)=\Omega(n^2)$

3.1-2

Using reasoning similar to what we used for insertion sort, analyze the running time of the selection sort algorithm from Exercise 2.2-2.

Inner loop in selection sort iterates $(n-i+1)$ times, for i = 1 to n-1, so the running time of selection sort is $\sum_{i=1}^{n-1} (n-i+1)=(n+2)(n-1)/2=\Theta(n^2)$

3.1-3

Suppose that $\alpha$ is a fraction in the range $0 < \alpha < 1$. Show how to generalize the lower-bound argument for insertion sort to consider an input in which the $\alpha n$ largest values start in the first $\alpha n$ positions. What additional restriction do you need to put on $\alpha$? What value of $\alpha$ maximizes the number of times that the $\alpha n$ largest values must pass through each of the middle $(1-2 \alpha)$ array positions?

At least $\alpha n$ values have to pass through at least $(1-2 \alpha)n$ times. insertion sort is at least proportional to $(\alpha n)(1-2 \alpha)n = \alpha(1-2\alpha)n^2 = \Omega(n^2)$ if $\alpha(1-2\alpha)=\Omega(1)$

$\max(\alpha(1-2\alpha))=\frac 1 8$ when $\alpha = \frac 1 4$