Consider the following selection sort algorithm, and assume that the input A is a random permutation ...

---

Consider the following selection sort algorithm, and assume that the input A is a random permutation of n distinct numbers. Calculate the expected number of times the line min <- j is executed, and express it using Theta notation. Selection-Sort(A): for i <- 1 to n - 1 do: min <- i; for j <- i + 1 to n do: if A[j] < A[min] then min <- j (this is the line to count); swap A[min] and A[i].