News for hackers. Stuff that matters.
Re:Functional Pearl 1 – The Min Missing Natural Number by xyzzyz on Thursday February 12, 2015 @05:32PM (#9041825)
The "responsive design" of this website uses two columns for web content when viewport is wide enough. This is supremely bad UX. Not only it is totally unexpected, as nobody on the web does it, it is also quite frustrating, as it forces you to scroll up to read second column.

I really hate it when people do that. This looks good in print, but the print is different medium with different constraints. Web is not print.

Re:Functional Pearl 1 – The Min Missing Natural Number by rnovak on Thursday February 12, 2015 @05:24PM (#9041786)

    >But we can skip out ideally half of the numbers.
ideally, but in the worst case it's O(n * (n - 1)), or O (n^2)

if your first X is the max, and your second choice is X-1, and so forth (in the worst case), then you're not operating in O(n), but n^2

Re:Functional Pearl 1 – The Min Missing Natural Number by smoyer on Thursday February 12, 2015 @06:46PM (#9042100)
You beat me to it ... if someone asks you for the complexity of a problem in Big-O notation, I'll always answer with the worst case.

I suppose answering with the average performance is useful if the routine is going to run a lot, but you'd better be careful even with that ... if the worst case is orders of magnitude bigger than the average, it may still matter.

Re:Functional Pearl 1 – The Min Missing Natural Number by jacksontale on Friday February 13, 2015 @04:08AM (#9043510)
Yeah, you are right, I should have mentioned that.
Re:Functional Pearl 1 – The Min Missing Natural Number by marvy on Sunday February 15, 2015 @07:46PM (#9054801)
But there's an easy fix: don't pick numbers from the given sequence, instead use binary search on [0,n]. Then you're guaranteed only log n iterations.
Re:Functional Pearl 1 – The Min Missing Natural Number by jacksontale on Sunday February 22, 2015 @07:32AM (#9089167)
Hi, I was using pure functional programming style, so list only.
Re:Functional Pearl 1 – The Min Missing Natural Number by marvy on Sunday February 15, 2015 @07:48PM (#9054805)
Another idea is to just stuff the input into a hash table and then say: is 0 there? is 1 there? ... is n-1 there?