2

I'm a bit confused with the performance guarantee and complexity of selection sort.

I checked through internet and the complexity of selection sort is O(n^2). This O(n^2) is in terms of time complexity, am i right?

So how about performance guarantee? Is the performance guarantee in my case measured in terms of swapping or in time complexity as well? If the performance guarantee is in terms of swapping, so best case of swapping is zero swaps (the array is already sorted) and the worst case of swapping is n-1 step? The performance guarantee is then equal to (n-1)/0=undefined, am I correct?

Please correct me if im wrong...or is the performance guarantee is in terms of running time? Then performance guarantee will be (n-1)/(n-1) = 1?

Can someone please clear my doubts?

Improve this question
  • You should take into account the comparisons too. Even if the array is already sorted, you need at least n - 1 comparisons to verify this. And worst case of swapping can be more than n - 1 steps, depending on the algorithm used. E.g. if I am not mistaken, with bubble sort it would be n*n/2. – Péter Török Sep 21 '11 at 8:16
  • Selection sort always swaps n-1 times afaik. Sometimes it swaps an element with itself, but I doubt the compiler can optimize this away everytime. Swapping of selection sort is thus Theta(n). – Falcon Sep 21 '11 at 8:28
  • so what is the difference between complexity and performance guarantee? as i know, the performance guarantee is (solution of the algorithm) / (optimal solution)? what is the optimal solution in this case?...confusing... – noobie Sep 21 '11 at 8:37
  • @noobie: What do you consider the optimal solution? Why wouldn't you implement it? Maybe the performance guarantee is more of a measurement for the grade of solutions of heuristic algorithms and has nothing to do with the time complexity. – Falcon Sep 21 '11 at 8:47
  • @Falcon: ''Maybe the performance guarantee is more of a measurement for the grade of solutions of heuristic algorithms''...heuristic algorithm does not always have optimal solution,right?so, performance guarantee is a grade for heuristic algorithm of how good the solution its obtain as compare to optimal solution, isn't it?so in this case, at most require n-1 steps of swapping to get sorted array, and as you said 'it swaps an element with itself' so, even it's given a sorted array, the selection sort still require n-1 step. so the performance guarantee is (n-1)/(n-1)=1, am i right? – noobie Sep 21 '11 at 9:00
3

"performance guarantee" is not a term typically used in analyzing algorithms.

Time complexity is measured in terms of whatever you want. You're stumbled on a dirty secret of CS - Big-O notation is often used rather sloppily without specifying what exactly increases with the input size in that manner. It's generally the number of some primitive operation that's assumed to dominate others in the implementation, and assumed to take constant time itself. Both of these assumptions are often not universally true. For example, for sorting algorithms time complexity is usually based on the number of comparisons. But comparing numbers is actually not a constant time operation itself if the numbers get realy big

Improve this answer
  • the reason for comparisons being the metric is that usually the expensive part is getting the two values brought into the cpu to compare. For systems where writes are the expensive, the metric may be the number of swaps. – user1249 Sep 21 '11 at 12:37
  • you might also find queue.acm.org/detail.cfm?id=1814327 an interesting read. – user1249 Sep 21 '11 at 12:38
1

Sometimes there is a difference between the big O of the average time vs. the big O of the worst case. For example, quicksort averages N*Log(N), but in theory you could get unlucky on the partition every time and end up with N**2.

In the case of selection sort both average and worst case are N**2, but it's still possible that "performance guarantee" was referring to the worst case performance.

Improve this answer
0

The algorithm complexity is in terms of whatever operation has the highest complexity. So, for example, if a sort requires O(n^2) comparisons and O(n log n) exchanges, the algorithm overall is O(n^2).

The rationale for this is simple -- big-O notation is about what happens as 'n' goes to infinity. As 'n' goes to infinity, whatever operation has the worst order will eventually dominate the execution time.

So is an algorithm requires O(n^2) of any sub-operation inside it, it's overall complexity cannot possibly be less than O(n^2).

Improve this answer
0

I'm a bit confused with the performance guarantee and complexity of selection sort.

I checked through internet and the complexity of selection sort is O(n^2). This O(n^2) is in terms of time complexity, am i right?

Right. It's the total number of constant factor * constant time operations dependent on the input size (this is still simplified).

So how about performance guarantee? Is the performance guarantee in my case measured in terms of swapping or in time complexity as well? If the performance guarantee is in terms of swapping, so best case of swapping is zero swaps (the array is already sorted) and the worst case of swapping is n-1 step? The performance guarantee is then equal to (n-1)/0=undefined, am I correct?

I don't know what you consider a performance guarantee, but the big O notation guarantees us, that an O(n^2) algorithm won't run slower than this bound indicates. A performance guarantee should not only be given in terms of swapping, you have to look at the whole algorithm. But you can explicitly ask for a performance guarantee for swapping in a specific algorithm, if that is of interest to you (for whatever reason). For selection sort this is Theta(n) as you always swap n-1 times with classic selection sort, the algorithm somtimes swaps an item with itself (which is still not a zero time operation, because I doubt the compiler can optimize it away in every case).

Please correct me if im wrong...or is the performance guarantee is in terms of running time? Then performance guarantee will be (n-1)/(n-1) = 1?

In my opinion, performance guarantee is a measurement for the grade of solutions of heuristic algorithms. You simply compare the approximated solution to the known optimal solution and calculate how close it really is. I am not completely sure about this, though.

If I had to apply this to sort of thinking to sorting algorithms that swap, then I'd argue that the best case for swapping is always O(n). And as selection sort swaps Theta(n) times the "performance guarantee for swapping" is probably 1. When I want to guarantee something, then I am usually concerned about the worst kinds of behaviour. So in the worst case an optimal solutions swaps n-1 times and so does selection sort. It'd be pointless to take the best case of an optimal solution.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.