i‑inci order statistic’i elde etmek için rastgele seçim yapıldığında ortalama karmaşıklığın o(n) olduğunu nasıl ispatlayabilirim?

Rastgele pivot seçildiğinde, her bölünmede beklenen alt dizi boyutu n/2 olur; bu yüzden T(n)=T(n/2)+O(n) denklemi çözülür ve ortalama çalışma süresi Θ(n) olarak elde edilir.