Why the first regex only looks from 11 to 13? how about 14,15...19?

how is this so? just curious

I agree. changing prototype is not a good practise. But using filter method is good.

Nice.

@computerguy103 I got a binary search that finishes in O(n log n)

No, you're right about that; a loop inside a loop is O(n^2) only if both loops grow proportionately to n. My instinctive thought was that yours had to be (both startPoints and endPoints should potentially return larger output lists as the input list grows larger), so it was a matter of figuring out what input best illustrated this.

My first few attempts at crafting a worst-case input failed because I hadn't looked closesly enough yet to see that some worst-case inputs to startPoints will result in a zero-length array from endPoints, and vice versa, so it wasn't quite as simple as that, but my original hunch still proved correct.

It's still a really fast solution, though; it's much faster than mine (which is also O(n^2)).

I was going for simplicity more than speed, partly because I didn't think there was any way to complete it in less than O(n^2). So if you can get a working solution that's O(n log n) I'd love to see it.

Nice! Thanks. You've definitely convinced me about this algorithm, though I absolutely disagree with the idea than any "loop inside a loop" is n^2, unless each of those loops grow proportionately to n. These both do, though.

In light of this test, I'm thinking the best way is to abandon the strategy entirely and use binary search to get O(nlogn)

http://jsperf.com/largest-gap/6

I added two tests with 50k and 100k descending pairs of numbers (n, n, n-2, n-2, n-4, n-4, etc.). The 100k descending array takes 4x longer than the 50k descending array, as you'd expect from an O(n^2) algorithm.

(Initially I tried 500k and 1m elements, but 500k took so long that I killed the process and started with something more reasonable. Even the 100k descending array takes significantly longer to process than your 1m small gap array.)

Neither loop's size grows proportionately to N unless each element is smaller than the previous, in which case each element in the 2nd loop will fail the max gap test and break, thus running in O(n) time.

The way I see it, you're reducing n by a factor, but big-O notation ignores this. You're still running a loop inside a loop, so it's O(n^2).

The actual runtime of this is something like t(n + n + c^2n^2), where c is a small value (close to zero). But it's still a polynomial of degree 2.

It's a fast algorithm, I'll give you that.

JS Perf would disagree. Based on the most demanding type of input sets I've seen it's about O(n). If you can find any sort of input for which it's n^2, please share!

http://jsperf.com/largest-gap/5

I know what Big-O means. Why do you say it's O(n^2)?

Can you give any example input that would cause this behavior? I don't think that's possible given the use of critical points and aborting for any gap of equal or lesser size to those already found.

Clever, but this is still O(n^2).