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

Question

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.

Answer 1

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)