Functional Pearl 1 – The Min Missing Natural Number | Hacker News Reader

Functional Pearl 1 – The Min Missing Natural Number

typeocaml.com

17 pointslelf7 comments

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.

    >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

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.

Yeah, you are right, I should have mentioned that.

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.

Hi, I was using pure functional programming style, so list only.

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?

Reply on news.ycombinator.com