n = |S|
m = |S
i
|
Expected Computational Complexity – like QuickSort
Since we know T(n-1) is O(n
2
):
With this result we can restate T(n) as:
Solve Recurrence
Relation
If we assume the
partition sizes are
drawn from a
uniform distribution