The execution tree for \(C(4)\) is:
\label{fig:execution-tree}
The optimized version - using dynamic programming - of the algorithm in a) becomes:
Computes the numerical value for C(n) for average quicksort complexity
Input: n is the size of the problem.
Memory:
initialize mem[n] with 0
C(n):
if mem[n] = 0 then:
if n = 0 then:
mem[n] <- 1
end if
sum <- 0
for i: 0 .. n-1 do:
sum <- sum + C(i)
end for
mem[n] <- 2/n * sum + n
end if
return mem[n]
end
From the outset, it is obvious that the memory complexity is \(\mathcal{O}(n)\)
The cost of initializing the memory is: \(n\) The algorithm will do \(n\) fills.
= [draw,anchor=center,minimum size=3em, thin]
in 0,1,2,3,4 at (0,-) (m) \(m_\m\); (5.9/1.5 - /1.5,-) – +(0,); ; in 1,2,3,4
(5.9/1.5 - /1.5, -) circle(0.15em);
in 1, ..., (5.9/1.5 - /1.5, -+ 0.95) – +(-0.5,0);
\label{fig:lookup-calls}
It will also do: \(i - 1\) lookup for each \(i\), so the total complexity is:
\[\begin{aligned} T(n) &= n + n + \sum_{i=0}^{n-1} \left[i-1\right]\\ &= 2n + \sum_{i=0}^{n-1} i + \sum_{i=0}^{n-1} 1\\ &= 3n + \frac{n(n-1)}{2}\\ &= \frac{5n + n^2}{2}\\ &\in \mathcal{O}(n^2) \end{aligned}\]