Why selection sort best case notation (Omega notation) is n^2 and not just n?

0
votes

I am taking CS50 online, and on week 3 we learned about algorithms. When we made it to complexity of algorythms, the lecture said that worst case senario of selection sort is n^2, because the algorythm loops through the array, and every time it looks for the smallest element, so

Looping Through an Array (O(n)) * Linear Search in the Array (O(n)) = O(n*n) = O(n^2)

After that, the lecturer said that we will have the same proccess in best case senario (already sorted array). But, earlier, he said that the best case senario of linear search (Element is first in the array) is Ω(1), so I thought that the best case senario of selection sort will be

Looping Through an Array (Ω(n)) * Linear Search in the Array (Ω(1)) = Ω(n*1) = Ω(n)

Why am I wrong?

1
algorithmtime-complexitybig-oselection-sort
Linear search for the smallest in the array is Ω(n), not Ω(1). Therefore Ω(n^2) overall. - wohlstad
Searching a specific element will be Ω(1) is the best case (if the element is the first). But here we need the minimum which requires to check all elements. - wohlstad

1 Answers

0
votes

Thank to the commentors, I figured out what was my mistake. I thought that selection sort consists of Linear Search for Specific Element, whom best case senario is Ω(1) if the element is first, but actually, it consists of Linear Search for the Smallest Element, whom best case senario is Ω(n), because even if the smallest element is first, the algorithm will have to loop through the entire arry, so:

Looping Through an Array (Ω(n)) * Linear Search for the Smallest Element in the Array (Ω(n)) = Ω(n*n) = Ω(n^2)

Thanks for the commentors, you helped me a lot.