3 deleted 1 character in body edited Jan 6 '15 at 20:09 James Evans 65755 silver badges66 bronze badges Both of your sources refer to the "worst-case expected running time" of $$O(n \log n).$$ I'm guessing this refers to the expected time requirement, which differs from the absolute worst case. Quicksort usually has an absolute worst-case time requirement of $$O(n^2)$$. The worst case occurs when, at every step, the partition procedure splits an $$n$$-length array into arrays of size $$1$$ and $$n-1$$. This "unlucky" selection of pivot elements requires $$O(n)$$ recursive calls, leading to a $$O(n^2)$$ worst-case. Choosing the pivot randomly or randomly shuffling the array prior to sorting has the effect of rendering the worst-case very unlikely, particularly for large arrays. See Wikipedia for a proof that the expected time requirement is $$O(n\log n)$$. According to another source, "the probability that quicksort will use a quadratic number of compares when sorting a large array on your computer is much less than the probability that your computer will be struck by lightning." Edit: Per Bangye's comment, you can eliminate the worst-case pivot selection sequence by always selecting the median element as the pivot. Since finding the median takes $$O(n)$$ time, this gives $$\Theta(n \log n)$$ worst-case performance. However, since randomized quick-sortquicksort is very unlikely to stumble upon the worst case, the deterministic median-finding variant of quicksort is rarely used. Both of your sources refer to the "worst-case expected running time" of $$O(n \log n).$$ I'm guessing this refers to the expected time requirement, which differs from the absolute worst case. Quicksort usually has an absolute worst-case time requirement of $$O(n^2)$$. The worst case occurs when, at every step, the partition procedure splits an $$n$$-length array into arrays of size $$1$$ and $$n-1$$. This "unlucky" selection of pivot elements requires $$O(n)$$ recursive calls, leading to a $$O(n^2)$$ worst-case. Choosing the pivot randomly or randomly shuffling the array prior to sorting has the effect of rendering the worst-case very unlikely, particularly for large arrays. See Wikipedia for a proof that the expected time requirement is $$O(n\log n)$$. According to another source, "the probability that quicksort will use a quadratic number of compares when sorting a large array on your computer is much less than the probability that your computer will be struck by lightning." Edit: Per Bangye's comment, you can eliminate the worst-case pivot selection sequence by always selecting the median element as the pivot. Since finding the median takes $$O(n)$$ time, this gives $$\Theta(n \log n)$$ worst-case performance. However, since randomized quick-sort is very unlikely to stumble upon the worst case, the deterministic median-finding variant of quicksort is rarely used. Both of your sources refer to the "worst-case expected running time" of $$O(n \log n).$$ I'm guessing this refers to the expected time requirement, which differs from the absolute worst case. Quicksort usually has an absolute worst-case time requirement of $$O(n^2)$$. The worst case occurs when, at every step, the partition procedure splits an $$n$$-length array into arrays of size $$1$$ and $$n-1$$. This "unlucky" selection of pivot elements requires $$O(n)$$ recursive calls, leading to a $$O(n^2)$$ worst-case. Choosing the pivot randomly or randomly shuffling the array prior to sorting has the effect of rendering the worst-case very unlikely, particularly for large arrays. See Wikipedia for a proof that the expected time requirement is $$O(n\log n)$$. According to another source, "the probability that quicksort will use a quadratic number of compares when sorting a large array on your computer is much less than the probability that your computer will be struck by lightning." Edit: Per Bangye's comment, you can eliminate the worst-case pivot selection sequence by always selecting the median element as the pivot. Since finding the median takes $$O(n)$$ time, this gives $$\Theta(n \log n)$$ worst-case performance. However, since randomized quicksort is very unlikely to stumble upon the worst case, the deterministic median-finding variant of quicksort is rarely used. 2 added 405 characters in body edited Jan 6 '15 at 19:59 James Evans 65755 silver badges66 bronze badges Both of your sources refer to the "worst-case expected running time" of $$O(n \log n).$$ I'm guessing this refers to the expected time requirement, which differs from the absolute worst case. Quicksort alwaysusually has an absolute worst-case time requirement of $$O(n^2)$$. The worst case occurs when, at every step, the partition procedure splits an $$n$$-length array into arrays of size $$1$$ and $$n-1$$. This "unlucky" selection of pivot elements requires $$O(n)$$ recursive calls, leading to a $$O(n^2)$$ worst-case. Choosing the pivot randomly or randomly shuffling the array prior to sorting has the effect of rendering the worst-case very unlikely, particularly for large arrays. See Wikipedia for a proof that the expected time requirement is $$O(n\log n)$$. According to another source, "the probability that quicksort will use a quadratic number of compares when sorting a large array on your computer is much less than the probability that your computer will be struck by lightning." Edit: Per Bangye's comment, you can eliminate the worst-case pivot selection sequence by always selecting the median element as the pivot. Since finding the median takes $$O(n)$$ time, this gives $$\Theta(n \log n)$$ worst-case performance. However, since randomized quick-sort is very unlikely to stumble upon the worst case, the deterministic median-finding variant of quicksort is rarely used. Both of your sources refer to the "worst-case expected running time" of $$O(n \log n).$$ I'm guessing this refers to the expected time requirement, which differs from the absolute worst case. Quicksort always has an absolute worst-case time requirement of $$O(n^2)$$. The worst case occurs when, at every step, the partition procedure splits an $$n$$-length array into arrays of size $$1$$ and $$n-1$$. This "unlucky" selection of pivot elements requires $$O(n)$$ recursive calls, leading to a $$O(n^2)$$ worst-case. Choosing the pivot randomly or randomly shuffling the array prior to sorting has the effect of rendering the worst-case very unlikely, particularly for large arrays. See Wikipedia for a proof that the expected time requirement is $$O(n\log n)$$. According to another source, "the probability that quicksort will use a quadratic number of compares when sorting a large array on your computer is much less than the probability that your computer will be struck by lightning." Both of your sources refer to the "worst-case expected running time" of $$O(n \log n).$$ I'm guessing this refers to the expected time requirement, which differs from the absolute worst case. Quicksort usually has an absolute worst-case time requirement of $$O(n^2)$$. The worst case occurs when, at every step, the partition procedure splits an $$n$$-length array into arrays of size $$1$$ and $$n-1$$. This "unlucky" selection of pivot elements requires $$O(n)$$ recursive calls, leading to a $$O(n^2)$$ worst-case. Choosing the pivot randomly or randomly shuffling the array prior to sorting has the effect of rendering the worst-case very unlikely, particularly for large arrays. See Wikipedia for a proof that the expected time requirement is $$O(n\log n)$$. According to another source, "the probability that quicksort will use a quadratic number of compares when sorting a large array on your computer is much less than the probability that your computer will be struck by lightning." Edit: Per Bangye's comment, you can eliminate the worst-case pivot selection sequence by always selecting the median element as the pivot. Since finding the median takes $$O(n)$$ time, this gives $$\Theta(n \log n)$$ worst-case performance. However, since randomized quick-sort is very unlikely to stumble upon the worst case, the deterministic median-finding variant of quicksort is rarely used. 1 answered Jan 6 '15 at 5:15 James Evans 65755 silver badges66 bronze badges Both of your sources refer to the "worst-case expected running time" of $$O(n \log n).$$ I'm guessing this refers to the expected time requirement, which differs from the absolute worst case. Quicksort always has an absolute worst-case time requirement of $$O(n^2)$$. The worst case occurs when, at every step, the partition procedure splits an $$n$$-length array into arrays of size $$1$$ and $$n-1$$. This "unlucky" selection of pivot elements requires $$O(n)$$ recursive calls, leading to a $$O(n^2)$$ worst-case. Choosing the pivot randomly or randomly shuffling the array prior to sorting has the effect of rendering the worst-case very unlikely, particularly for large arrays. See Wikipedia for a proof that the expected time requirement is $$O(n\log n)$$. According to another source, "the probability that quicksort will use a quadratic number of compares when sorting a large array on your computer is much less than the probability that your computer will be struck by lightning."