(1.14) Starting relation, valid for $N > 0$:
$$A_N = 1 + \frac{2}{N} \sum_{j=1}^{N}{A_{j-1}}$$ This leaves uncertainty for the value of $A_0$, we will settle for $A_0 = 0$.
Multiplying by $N$ we have: $$N A_N = N + 2\sum_{j=1}^{N}{A_{j-1}}$$ The equation above for $N-1$ is: $$(N - 1)A_{N-1} = N - 1 + 2\sum_{j=1}^{N-1}{A_{j-1}}$$ Subtracting the two: $$N A_N - (N - 1)A_{N-1} = 1 + 2A_{N-1}$$ $$N A_N = (N + 1)A_{N-1} + 1$$ which corresponds to: $$\frac{A_N}{N+1} = \frac{A_{N-1}}{N} + \frac{1}{N(N+1)} = \frac{A_{N-2}}{N-1} + \frac{1}{(N-1)N} + \frac{1}{N(N+1)}$$ that goes all the way down to: $$\frac{A_N}{N+1} = \frac{A_0}{1} + \sum_{k=1}^{N}{\frac{1}{k(k+1)}} = \sum_{k=1}^N{\frac{1}{k(k+1)}}$$ the last step assuming //(A0 = 0//) as we did in the beginning.
The summation in the right hand side can be easily solved: $$\sum{k=1}^N{\frac{1}{k(k+1)}} = \sum{k=1}^N{(\frac{1}{k}-\frac{1}{k+1})}$$ $$= \sum{k=1}^N{\frac{1}{k}} - \sum{k=1}^N{\frac{1}{k+1}}$$ $$= \sum{k=1}^N{\frac{1}{k}} - \sum{k=2}^{N+1}{\frac{1}{k}}$$ $$= 1 + \sum{k=2}^N{\frac{1}{k}} - \sum_{k=2}^{N}{\frac{1}{k}} - \frac{1}{N+1}$$ $$= 1 - \frac{1}{N+1}$$ So:<br> $$\frac{A_N}{N+1} = 1 - \frac{1}{N+1} \Rightarrow A_N = N$$

(1.15) Show that the average number of exchanges used during the first partitioning stage (before the pointers cross) is $\frac {(N-2)}{6}$. (Thus, by linearity of the recurrences, $B_N = \frac {1}{6}C_N - \frac {1}{2} A_N$).

The expected number of exchanges given that $i$ is the rank of the pivot chosen is given by the expected number of elements of rank more than $i-1$ in the first $i-1$ elements of the array. $$ \mathbb{E}[ \text{no of exchanges} | \text{pivot of rank }i] = \sum_{j =1}^{i-1} \mathbb{E}[\mathbb{I}( j\text{-th element has rank }> i )]$$ which gives us that, $$ \mathbb{E}[ \text{no of exchanges} | \text{pivot of rank }i] = \sum_{j =1}^{i-1} \frac{N-i}{N-1} = \frac{(i-1)(N-i)}{N-1}$$ Thus the number of exchanges is $$ \mathbb{E}[ \text{no of exchanges}] = \sum_{i =1 }^N \frac{1}{N(N-1)} (Ni - i^2 + i - M )$$ Thus $$ \mathbb{E}[ \text{no of exchanges}] = \frac{1}{N(N-1)}\left( N\sum_{i=1}^N (i-1) - \sum_{i=1}^N (i-1)^2 - \sum_{i=1}^N (i-1) \right)$$ which gives us that $$ \mathbb{E}[ \text{no of exchanges}] = \frac{1}{N(N-1)}\left( \frac{N^2(N-1)}{2} - \frac{(N-1)N(2N-1)}{6} - \frac{N(N-1)}{2} \right)$$ Thus $$ \mathbb{E}[ \text{no of exchanges}] = \frac{N}{2} - \frac{(2N-1)}{6} - \frac{}{2} = \frac{N-2}{6}$$ giving the required answer.

If we change the first line in the quicksort implementation above to: $$if\ r-l<=M\ then\ insertionsort(l,r)\ else$$ (see §7.6), then the total number of compares to sort N elements is described by the recurrence $$C_N=\begin{cases}N+1+\displaystyle{1\over N}\sum_{1\le j\le N} (C_{j-1}+C_{N-j})&N>M;\\{1\over4}N(N-1)&N\le M\\\end{cases}$$ Solve this exactly as in the proof of theorem 1.3.

Following the analysis from lecture, we have that, $$ \frac{C_N}{N+1} = \frac{C_M}{M+1} + 2 \sum_{M+2 \le k \le N+1} \frac{1}{k}$$ Thus $$ \frac{C_N}{N+1} \approx \frac{M}{4} + 2 \log(\frac{N+1}{M+1})$$ This gives us that $$ C_N \approx N (\frac{M}{4}-2\log(M+1)) + 2 N \log N$$

(1.18) Ignoring small terms (those significantly less than N) in the answer to the previous question, find a function $f(M)$ so that the number of comparisons is approximately $2N\ln N+f(M)N$. Plot the function $f(M)$, and find the value of $M$ that minimizes the function.

It is around 9-10