Our algorithm for calculating a numerical value is, in pseudocode:
Computes the numerical value for C(n) for average quicksort complexity
Input: n is the size of the problem.
C(n):
if n = 0 then:
return 1
end if
sum <- 0
for i: 0 .. n-1 do:
sum <- sum + C(i)
end for
return 2/n * sum + n
end
The complexity of this algorithm in turn is:
\[\begin{aligned} T(n) = \begin{cases} c_0 & \text{if } n = 0\\ c_1 + \displaystyle\sum_{i = 0}^{n-1} T(i) & \text{if } n > 0 \end{cases}\end{aligned}\]
\(T(n-1), n > 1\) is, using the recursive definition above: \[T(n-1) = c_1 + \sum_{i = 0}^{n-2} T(i)\]
Using this, we expand \(T(n)\) and get:
\[\begin{aligned} T(n) &= c_1 + \sum_{i = 0}^{n-2} T(i) + T(n-1)\\ &= 2T(n-1)\end{aligned}\]
Thus we get:
\[\begin{aligned} T(n) = \begin{cases} c_0 & \text{if } n = 0\\ 2^{n-1}(c_0 + c_1) & \text{if } n > 0 \end{cases}\end{aligned}\]
Meaning \(T(n) \in \mathcal{O}(2^n)\).