Why is the time complexity of nested while loops in Quicksort not O(n^2)?

user_13933254 0
Viewed 246
def partition(l, h):
    i, j = l, h
    while i < j:
        while arr[l] > arr[i]:
            i += 1
        while arr[j] > arr[l] and j >= 0:
            j += 1
        if i < j:
            arr[i], arr[j] = arr[j], arr[i]
    arr[l], arr[j] = arr[j], arr[l]
    return j

The time complexity of nested while loops is O(n2), the above snippet code is from Quicksort. Then how is the overall time complexity O(n log n)?

nested-loops quicksort while-loop python
1 Answers

The partition function takes linear time -- as the comments point out, the size of the list you're partition decreases, allowing for the possibility of an O(n log n) runtime.

However, quicksort runs in O(n^2) if your choice of partition point is poor. For example, consider the case when your partition chooses the largest element in the array that hasn't already been a partition. Then the runtime can be expressed as T(n) = T(n - 1) + O(n) ==> O(n^2).

However, randomly choosing the partition gives an O(n log n) expected time. If you want an O(n log n) runtime in the worst-case, you can use a deterministic median finding algorithm, such as the one given in these slides, to find a good partition. (These slides also give a formal proof of the expected runtime of randomized quicksort.)

user_177698150
Related