5 ms·
Functional Pearl 1 – The Min Missing Natural Number
- rnovak 12y ago>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
- smoyer 12y agoYou 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.
- jacksontale 12y agoYeah, you are right, I should have mentioned that.
- marvy 12y agoBut 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.
- jacksontale 12y agoHi, I was using pure functional programming style, so list only.
- xyzzyz 12y agoThe "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.
- deleted 12y ago[deleted]
- marvy 12y agoAnother idea is to just stuff the input into a hash table and then say: is 0 there? is 1 there? ... is n-1 there?