News for hackers. Stuff that matters.
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.