On average, how many comparisons does Quicksort require to sort 1000 records (to the nearest 1000 comparisons)?

10000

    What is Quicksort's average case running time?

    It is \Theta(n \log n)

    This means about 10 \cdot 1000 comparisons are required