So, i haven't seen a question like this before, and my answer is one i got from a bunch of different sources online. Could someone verify that it is correct and explain how to answer similar questions?
more specifically, is the last line based on a formula and how do i find the number of comparisons?
Q:Find the worst case time complexity of the selection sort algorithm
for the swap operation and the comparison operation.
A:Selection sort chooses largest or smallest item in array and places the item in its correct place. Then it selects next larger or smaller item and keeps it in serial order. The process is repeated until all the elements are sorted.
In below diagram, 8 was omved from index 1 to index 4 as it was largest. then 7 was swapped and then 6 and so on until the array was sorted at last.
Swap function interchange value x and y.
Starting from index 1 to index 4, the largest value in the array will be searched. In pass 1, the largest value is 8 and was found at index 1. Therefore value at index 1 (8) will be swap with value at index last(4). There are 4 comparisons in this pass.
Number of Comparisons: 4 + 3 + 2 + 1 = 10
For array n= 5 => (n-1) + (n-2) + ….+ 2 + 1 = n(n-1)/2 = O(n2) (Comparisons) Time complexity for worst case. For swap: O(n)
Best Answer
You're almost there, but you never answer your question. Let's assume that we sort by using the largest element.
Suppose we have $n$ elements, in the first pass we must scan through all $n$ of these and compare to find the largest among them. Once we've done this we can swap with the last element in the list, in the next pass we have $n-1$ unsorted elements so we have to go through all of these. So after the $i$-th iteration we have a sorted sublist of length $i$ at the end.
In total we do $$ (n-1)+(n-2)+\dots+(2)+(1)=\frac{n(n-1)}{2} \in O(n^2)$$ comparisons.
The swap function takes two elements and swaps them, it does not depend on the number of elements so it requires a constant time and is hence $O(1)$, there are $n-1$ of these swaps, so the "swapping complexity" is $O(n)$.
Remember that the order of a problem is the same as the maximum order of it's constituent parts so selection sort has time complexity $O(n^2)$.
Selection sort has same time complexity on every input. In other cases you may have to look for the worst input for a problem (reversed input for bubble sort etc.), and consider the number of comparision/swaps that happen.