# Tag Info

The running time of quicksort satisfies the recurrence $$T(n) \leq \max_{n_1+n_2+1=n} T(n_1) + T(n_2) + Cn,$$ with base cases of $T(1) = C$ and $T(0) = 0$, say. Let us now prove by induction that $T(n) \leq Cn^2$. The base cases obviously hold. As for the inductive step, \begin{align} T(n) &\leq \max_{n_1+n_2+1=n} C(n_1^2 + n_2^2) + Cn \\ &= \max_{...
Given a line $L = b$, the distance from any point $(x, y)$ to $L$ is $\left| y - b\right|$. The sum of a distances for a set of points $S = \{(x_1, y_1), \dots, (x_n, y_n)\}$ is then $$\left| y_1 - b \right| + \cdots + \left| y_n - b \right|$$ which is minimized for which $b$?