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.
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