How is worst case time complexity of selection sort calculated? [Solved]

Question

So in worst case array to sort will be in descending order and we will get a time complexity of O(n power 2) right?

If there are 14 elements ,then in worst case loop will run only 91 times ,so what other factors are counted which results in n to the power 2 time complexity?

Answer 1

Abhay

Part 1/2

Even in best case Selection sort will cost you O(n²) in terms of comparison.

You see, whether you're given an array in decending, ascending or random order, selection sort works from left to right finding the smallest element in the array and swaps it with the element in the first position, then finds the second smallest element and swaps it with the element in the second position, and continues in this way until the entire array is sorted.

Suppose you have = { 1, 2, 3, 4}

First, it'll start from 1 and then 1 will be compared with the rest of the elements. so 1 will be compared with 2, then 3, then 4 (total comparison 3)
No swap required since 1 is smallest among 2,3 and 4.

Then it'll move to 2.
Similarly 2 will be compared with 3, then 4 ( total comparison 2)
No swap.

Then it'll move to 3 and compared it with 4. (total comparison 1)
No swap.

Then it'll finally reach 4, which is the last element.
(total comparison 0, which makes the end of comparison)
No swap.
Now your sorting is done

Answer 2

Part 2/2

So you see even in best case time complexity for comparison is 3 + 2 + 1

Try it with decending array you'll reach at the same conclusion.

Only difference is in the number of swaps required.
In ascending order array no swaps required but in decending order array you'll require 3 swaps for the array [4, 3, 2, 1] to be sorted.

In general when you're given with n number of elements the Time Complexity for Comparison will be calculated as-
(n-1) + (n-2) +.....+2 +1
= ((n-1) * n) /2
= n²/2 - n/2

Taking big-O
O(n²/2 - n/2)
=O(n²/2) - O(n/2)
=O(n²) - O(n)
= O(n²)

But for swaps
in worst case you'll need (n-1) swaps while in best case you'll need 0 swaps ( as seen in example)

So taking big-O
worst case :
O(n-1) = O(n)
best case :
O(0) = O(1)

p.s. Selection sort works in place so no extra auxiliary space required )
even in worst case it's O(1)

Answer 3

thank you very much

Answer 4

민호 🇰🇷 thank you very much