CODEWITHSUNDEEP
algorithmtime-complexityselection-sort
MNRC
MNRC

Reputation: 263

What is the running time of this modified selection sort algorithm?

I'm prepping for software developer interviews and reviewing algorithms. I'm stuck on a question that asks "Given a modified selection sort algorithm that returns in sorted order the k smallest elements in an array of size n what is its worst case running time in terms of n and k?"

Modified selection sort algorithm:

A = [1...n]  //an array of size n

for i = 1 to k
  smallest = A[i]
  for j = i + 1 to n
    if A[j] < A[smallest]
      smallest = j
  swap (A[i], A[smallest])

I'm guessing it's O(nk) but not sure why.

Upvotes: 1

Views: 475

Answers (2)

Abhishek Bansal
Abhishek Bansal

Reputation: 12705

The outer loop runs k times. For each iteration of outer loop, the inner loop makes O(n) iterations.

More mathematically, the inner loop runs:

(n-1) + (n-2) + (n-3) + .... + (n-k) times
= n*k - k*(k+1)/2
= k* (n - k/2 -1/2)
~ k * n

Hence, Complexity = O(n*k)

Upvotes: 3

Ayush
Ayush

Reputation: 2618

O(nk)

Outer loop picks k elements and inner loop picks n elements

Upvotes: 2

Related Questions