Computes the numerical value for C(n) for average quicksort complexity
Input: n is the size of the problem.
Memory:
initialize sum with 1
C(n):
if n = 0 then:
return 1
end if
sum <- 1
for i: 1 .. n-1 do:
sum = sum + 2/i * sum + i
end for
return 2/n * sum + n
end
The complexity of this algorithm is:
\[\begin{aligned} T(n) &= c_0 + \sum_{i=1}^{n-1} c_1\\ &= c_0 + c_1 + c_1 n\\ &\in \mathcal{O}(n) \end{aligned}\]