Израчунавање просечне сложености на основу дефиниције би подразумевало да се израчуна просечан број корака за све могуће улазе дате димензије тј. да се саберу бројеви потребних корака за све могуће улазе дате димензије и да се затим добијени број подели са бројем могућих улаза те димензије. У пракси се обично просечна сложеност израчунава мало другачије, тако што се могући улази поделе у класе у којима се сви проблеми решавају у истом броју корака и израчуна се просек броја корака по свим класама. На пример, код алгоритама сортирања обично није битно који се конкретни бројеви јављају на улазу док год је распоред њихових величина исти (на пример, сви улази који су унапред сортирани припадају истој класи). Наравно, да бисмо на овај начин добили исти резултат, морамо да знамо да су све класе подједнако вероватне или, ако нису, да у коначну рачуницу укључимо и вероватноће појављивања улаза сваке класе.
Анализа просечне сложености може бити кориснија од сложености најгорег случаја ако се покаже да се најгори случајеви ретко појављују у пракси. Захваљујући овој анализи може се оправдати коришћење алгоритама који имају лошију сложеност најгорег случаја, али бољу просечну сложеност и тога су у применама бржи. Типичан пример је однос алгоритма сортирања обједињавањем чија је сложеност најгорег случаја \(O(n\log{n})\) са алгоритмом брзог сортирања чија је сложеност најгорег случаја \(O(n^2)\), али захваљујући својој просечној сложености \(O(n\log{n})\) у пракси даје боље резултате од сортирања обједињавањем. У наставку ћемо приказати анализу просечне сложености управо на примеру алгоритма брзог сортирања.
Упечатљиво својство алгоритма QuickSort је ефикасност у пракси насупрот квадратној сложености најгорег случаја. Ово запажање сугерише да су најгори случајеви ретки и да је просечна сложеност овог алгоритма осетно повољнија.
Претпоставимо да је једнака вероватноћа да ће произвољни елемент бити изабран за пивот и да је једнака вероватноћа да пивот након партиционисања заврши на било којој позицији од \(0\) до \(n-1\). Ако бројимо само упоређивања (број замена је мањи или једнак броју упоређивања), сложеност партиционисања је \(n-1\). Тада просечна сложеност задовољава наредну рекурентну једначину.
\[T(n) = n-1 + \frac{1}{n}\sum_{i=0}^{n-1} \left(T(i) + T(n-i-1)\right)\]
Први сабирак се креће од \(T(0)\) до \(T(n-1)\), а други од \(T(n-1)\) до \(T(0)\), тако да се свако \(T(i)\) јавља тачно два пута. Зато за \(n \geq 1\) важи
\[T(n) = n-1 + \frac{2}{n}\sum_{i=0}^{n-1}T(i).\]
Ово је такозвана једначина са потпуном историјом, јер се вредност \(T(n)\) израчунава преко свих претходних вредности \(T(i)\). Један начин да се историја елиминише је да се посматрају разлике између суседних чланова низа чиме се добија једначина која описује везу између два суседна члана. У овом случају се сваки од сабирака \(T(i)\) дели са \(n\), те пре одузимања сваки од узастопних чланова треба помножити са одговарајућим фактором. Тако се добија
\[\begin{align*} nT(n) - (n-1)T(n-1) &= \left(n(n-1) + 2\sum_{i=0}^{n-1}T(i)\right) -\\ &\quad \left((n-1)(n-2) + 2 \sum_{i=0}^{n-2}T(i)\right)\\ &= 2(n-1) + 2T(n-1) \end{align*}\]
Зато је
\[T(n) = \frac{2(n-1)}{n} + \frac{n+1}{n}T(n-1)\]
Иако је ова једначина линеарна рекурентна једначина која повезује само два узастопна члана низа, она није са константним коефицијентима и потребно је мало инвентивности да бисмо је решили. Дељење са \(n+1\) нам даје погоднији облик.
\[\frac{T(n)}{n+1} = \frac{T(n-1)}{n} + \frac{2(n-1)}{n(n+1)}\]
Наиме, сада се види да су два члана која укључују непознату функцију \(T(n)\) истог облика, па једначину можемо једноставно одмотати и коришћењем чињенице да је \(T(0) = 0\) добити
\[\frac{T(n)}{n+1} = \frac{2(n-1)}{n(n+1)} + \frac{2(n-2)}{(n-1)n} + \ldots + \frac{2\cdot (1-1)}{1(1+1)} = 2\sum_{i=1}^{n} \frac{i-1}{i(i+1)}\]
Централно питање постаје како израчунати збир
\[\sum_{i=1}^{n} \frac{i-1}{i(i+1)}\]
Томе помаже раздвајање сабирака на парцијалне разломке. Из једначине
\[\frac{i-1}{i(i+1)} = \frac{A}{i} + \frac{B}{i+1}\]
следи да је \(Ai + A + Bi = i - 1\), па је \(A = -1\), \(B = 2\) и важи
\[\frac{i-1}{i(i+1)} = \frac{2}{i+1} - \frac{1}{i}\]
Зато је
\[\sum_{i=1}^{n} \frac{i-1}{i(i+1)} = \frac{2}{1+1} - \frac{1}{1} + \frac{2}{2+1} - \frac{1}{2} + \frac{2}{3+1} - \frac{1}{3} + \ldots + \frac{2}{n+1} - \frac{1}{n}\]
Можемо груписати разломке са истим имениоцем и добити
\[\sum_{i=1}^{n} \frac{i-1}{i(i+1)} = \frac{1}{2} + \ldots + \frac{1}{n} - 1 + \frac{2}{n+1}\]
Зато је
\[T(n) = 2(n+1)\cdot\left(1 + \frac{1}{2} + \ldots + \frac{1}{n}\right) - 4n.\]
Знамо да се хармонијски збир \(1 + 1/2 + \ldots + 1/n\) асимптотски понаша као \(\log{n} + \gamma\), где је \(\gamma\) Ојлер-Маскеронијева константа \(\gamma \approx 0,57722\) и зато је
\[T(n) = \Theta\left(2(n+1)(\log{n} + \gamma) - 4n\right) = \Theta(n \log{n}).\]