4 ms·
>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 c
by 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.