0

I am not sure of what will be the time complexity of the Quickselect algorithm (for kth largest element), so can anyone please help me out

def swap(arr,i,j):
    temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp

def partition(arr,left,right,p_index):
    pivot = arr[p_index]
    i = left-1

    for j in range(left,right):
        if arr[j] >= pivot:
            i += 1
            swap(arr,i,j)
    swap(arr,i+1,p_index)
    return i+1


def quickselect(arr,left,right,k):
    if left == right:
        return arr[left]

    p_index = right
    p_index = partition(arr,left,right,p_index)

    if p_index == k:
        return arr[p_index]
    elif p_index > k:
        return quickselect(arr,left,p_index-1,k)
    else:
        return quickselect(arr,p_index+1,right,k)
saurav
  • 9
  • 1
  • 1
    https://stackoverflow.com/questions/56940793/quickselect-time-complexity-explained#:~:text=%22However%2C%20instead%20of%20recursing%20into,(n%5E2).%22 – leoOrion Jul 23 '21 at 03:24
  • 1
    One of the problems with quicksort and quickselect is that the average time complexity is markedly different from the worst cast time complexity. – Tim Roberts Jul 23 '21 at 03:40

1 Answers1

0

Average time complexity is reduced from O(n log(n)) to O(n), but worst case remains at O(n^2).

https://en.wikipedia.org/wiki/Quickselect

rcgldr
  • 27,407
  • 3
  • 36
  • 61