search

imposters-handbook / feedback

General typos, issues, clarifications etc for The Imposter's Handbook
78 stars 2 forks source link

Incorrect worst case complexity for selection sort #10

Closed luddd3 closed 8 years ago

luddd3 commented 8 years ago

In Datastructures and Algorithms -> Selection sort

I think this paragraph is incorrect:

Oddly, the worst case complexity (the list is already sorted) is O(1), which makes this an interesting choice if there's a chance of sorting a pre-sorted list (or a list of equal objects). In all other cases this algorithm is O(N^2), which means N operations per N items.

Could it be that you were thinking of auxiliary space, which is O(1)?

robconery commented 8 years ago

Wow I messed that up didn't I. Hmmm. Fixed - thanks :)