How do I distinguish the $2$ cases in the snippet below on the minus $4$th line ? I.e. I do not follow the last line which says: considering separately the case $k<n/2$ and the case $k\geq n/2$. How do I compute $$cn+\frac{10c}{n}(\frac{n^2}{2}+\frac{kn}{2}-\frac{k^2}{2.5}) \leq cn+\frac{10c}{n}\frac{9n^2}{10}$$ by distinguishing the two cases ??
Also I would like to understand what it means in the Claim $7.4$ this sentence:
Let $T(n) \text{ be the maximum of } T(k,a_1,\ldots,a_n) \text { over all $n$ length inputs }.$
I.e. what are $n$ length inputs $T(k,a_1,\ldots,a_n)$ - what is the length of $k$, say, in $T(k,a_1,\ldots,a_n)$ ?
When you mention the length of $k$, note that we're really after the $k$th element in an unsorted sequence. The elements are labelled as $a_1$, $a_2$, $a_3$, etc. up to $a_n$. The algorithm picks a random index in the set, more specifically the $i$th element $a_i$, and counts the number of elements less than it. Then it either finishes, or branches recursively.
Now, in the analysis, we consider all possible running times of the algorithm, and label them $T(k, a_1, a_2, \dots, a_n)$. Then, $T(n)$ is defined as the maximum running time out of all of these times, for length $n$.
I believe what the author intends, when they mention about considering the two cases seperately, is to consider replacing $k$ by $n/2$, which works in both cases:
$$cn + \frac{10c}{n} \left( \frac{n^2}{2} + \frac{kn}{2} - \frac{k^2}{2.5} \right) = $$ $$cn + \frac{10c}{n} \left( \frac{n^2}{2} + \frac{(n/2)n}{2} - \frac{(n/2)^2}{2.5} \right) = $$ $$cn + \frac{10c}{n} \left( \frac{n^2}{2} + \frac{n^2}{4} - \frac{(n)^2}{10} \right) < $$ $$cn + \frac{10c}{n}\frac{65n^2}{100}$$
I'm not sure I quite catch the reference that the author is considering, but the simple math checks out by replacing $k$ by $n/2$, which is the worst case in both cases.