Both the deterministic and randomized quicksort algorithms have the same best-case running times of [math]O(n \lg n)[/math] and the same worst-case running times of [math]O(n^2)[/math]. The difference is that with the deterministic algorithm, a particular input can elicit that worst-case behavior. With the randomized algorithm, however, no input can always elicit the worst-case behavior. The reason it matters is that, depending on how partitioning is implemented, an input that is already sorted--or almost sorted--can elicit the worst-case behavior in deterministic quicksort.