CODEWITHSUNDEEP
sortingiterationtime-complexitybig-oselection-sort
Engineer999
Engineer999

Reputation: 3955

Why is the time complexity of the selection sort algorithm O(n2)

Let's take an array of 5 numbers for example and we wish to sort them using the selection sort algorithm.

On the first iteration, we will iterate over the the 5 numbers and swap the lowest number found with element at index 0.

The next iteration starts at index 1, and iterates over the other 4 numbers doing the same, next iteration, start at index 2 and iterate over the 3 numbers etc.

There will therefore be 5 + 4 + 3 + 2 = 14 index checks. If time complexity is stated as O(n2), then shouldn't this be 25? I understand the bubble sort algorithm having time complexity of O(n2), but not this.

Upvotes: 0

Views: 836

Answers (1)

otokkk
otokkk

Reputation: 21

I think you dont understand the real meaning of big O notation, the example that you provided is not valid. "big O notation is used to classify algorithms according to how their run time or space requirements grow as the input size grows". Moreover it does not provide exact information(count of steps to make) for small size inputs. For more info you can visit link: https://en.wikipedia.org/wiki/Big_O_notation

Upvotes: 2

Related Questions