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)
Muskan is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
3
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
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.
0