Question: Let $T(n)$ be the expected running time of find-index. Write a recurrence relation for T(n) and then solve it.
So random(n) takes constant time. The average running time should have a $\frac{1}{n}$ chance of selecting the pivot. How do I write?
There are two cases. Either you find $k$ on the first try, or you don't.
The first case happens with probability $1/n$. In that case, the algorithm runs for $1$ step.
The second case happens with probability $1-1/n$. In that case, the algorithm runs for $1+T(n)$ steps on average. The $1$ is for the first check, while the $T(n)$ accounts for all subsequent checks.
Putting this all together, $$ T(n) = \tfrac1n \cdot 1 + (1-\tfrac1n)\cdot (1+T(n)) $$ This recursivley expresses $T(n)$ in terms of itself.