Chris Angelico <rosuav <at> gmail.com> writes: > > > Sort cannot be O(log(n)) and it cannot be faster than a standard O(n) > > minimum finding algorithm. No valid sorting algorithm can have even a > > best case performance that is better than O(n). This is because it > > takes O(n) just to verify that a list is sorted. > > Or looking at it another way: Sorting a list will require, at a bare > minimum, comparing every element against at least one other element - > if you could reduce it below that, there would be some element whose > position you cannot know. Finding the minimum requires precisely that > number of comparisons: each item against the one current minimum. :) > > ChrisA >
Shame on me! You really shouldn't post things, while working on something else that needs all your attention. You're absolutely right with what you're saying. I was so fixed on speeding things up with the use of bisect that I wasn't really thinking carefully about the sorting, and I was delighted when I saw that my solution was speeding up the range() input example. Unfortunately, it's only speedy for this example because the input is actually sorted from the start (so sorted just checks the list -> O(n)). When you use it on shuffled input, performance is really poor as opposed to the simple min() solution, so as pointed out by you the costs of sorting are higher than the gain from using bisect. What started this whole mess was my gut feeling that you should somehow be able to exploit all the information you have, and that is that the second minimum you're looking for cannot be negative, so is at least 0 (or 1 depending on how you decide to treat 0). So I thought that under this restriction there should be a faster way to find the minimum than with min(). It only fooled me into thinking that bisect could be used for it though. Is it really impossible to beat the min() solution then? Thanks for your feedback, Wolfgang -- http://mail.python.org/mailman/listinfo/python-list
