How do I find the average case for the KthLargest alrorithm?

  analysis, average, c++

I understand that the best case would be B(1). Will the worst case be W(n+1) since when searching the list, since you have to compare both sides of the last element. The main thing I am confused on is the average case for this algorithm.

findKthLargest (list, N, K)
for i = 1 to K do
    largest = list[1]
    largestLocation = 1
    for j = 2 to N-(i-1) do
        if list[j] > largest then
            largest = list[j]
            largestLocation = j
        endIf
    endFor
    swap(list[N - (i-1)], list[largestLocation] )
endFor
return largest

Source: Windows Questions C++

LEAVE A COMMENT