CODEWITHSUNDEEP
algorithmsortingselection-sort
Muskan
Muskan

Reputation: 21

selection sort algorithm time complexity

In selection sort the outer loop time complexity will be O(n) and the inner loop time complexity will be (n(n-1))/2 then why have we added outer loop time complexity with inner loop : n + (n(n-1))/2 instead of multiplying?

As it is a nested loop then it must be multiplied. But if we multiply the time complexity, it will become O(n^3) instead of O(n^2)

Upvotes: 2

Views: 64

Answers (2)

trincot
trincot

Reputation: 350781

You asked:

why have we added outer loop time complexity with inner loop : n + (n(n-1))/2 instead of multiplying?

It is correct that in total the inner loop makes š‘›(š‘›āˆ’1)/2 iterations, but those iterations are not the only work that is done. On top of that there is code outside that loop that executes š‘›āˆ’1 times, and then a final comparison of the outer for that doesn't result in an iteration.

So yes, you would consider the complexity to be:

Ā  O(š‘› + š‘›(š‘›āˆ’1)/2)

But this additional š‘› really is irrelevant in terms of big O. The above big O expression is equivalent to:

Ā  O(š‘› + š‘›(š‘›āˆ’1)) = O(š‘› + š‘›Ā²) = O(š‘›Ā²)

Check out the rules on how you can simplify big O expressions on Wikipedia

Upvotes: 2

m-sarabi
m-sarabi

Reputation: 2305

In selection sort, the inner loop runs n - 1 times in the first iteration, n - 2 times in the second iteration, and so on until it runs 1 time in the last iteration.

The outer loop controls how many times the inner loop iterates.

The sum of the first n - 1 natural numbers is n * (n - 1) / 2, which has a complexity of O(n^2).

I encourage you to read the Selection sort article on Wikipedia.

Upvotes: 1

Related Questions