Assume we are using the selection sort algorithm For an arra

Assume we are using the selection sort algorithm. For an array of n elements, fill in the following table using the Big-O notation:

Solution

SELECTION_SORT (Array)

for i <= 1 to arrayLength-1 do
min j <= i;
min temp <= Array[i]
for j <= i + 1 to arrayLength do
If Array[j] < min temp then
min j <= j
min temp <= Array[j]
Array[min j] <= Array [i]
Array[i] <= min temp

Since comparison is done inside the nested loop, thus total comparisons will be n² in both worst and best cases. after each of the n-1 passes to find the smallest remaining element, the algorithm performs a swap to put the element in place, thus there will be (n-1) swaps. SInce the array is already sorted, there won;t be any swaps in best case.

  

	WORST CASE	BEST CASE
#COmparisons	n2	n2
#Swaps	n	0