But wait, O(2n) and O(n) are the same aren't they? Eg both linear, constant factor doesn't make a difference to the time complexity. Or did you mean to write O(2^n) or something?

You're correct. The point of O(f(n)) notation is asymptotic complexity. Intuitively, this measures how the runtime grows as the input grows--whether the solution does one pass or two over the input, doubling the input will double the runtime, so it's linear.

Regarding the GP's approach in general, chasing constant-factor improvements on problems like this isn't always worth it. Doing one pass isn't necessarily faster than two if (for example) you do twice as much work at each step.

Not to mention that measuring performance in "number of operations" is pretty vague to begin with unless you're digging all the way down to the generated assembly code and know how many clock cycles an ADD takes vs a MUL, etc. At that point you should probably just pull out a profiler =)

> But wait, O(2n) and O(n) are the same aren't they?

I guess it depends on where you work, I guess I've grown used to the more accurate complexities we use around here and forgot about the concrete theory. For us, twice the time is twice the time no matter how you sugar coat it.

So, uh, my bad. You are correct.

> For us, twice the time is twice the time no matter how you sugar coat it.

Which is funny, because your method still uses 2n multiplications, it just computes them in the same loop.

Well I look silly don't I. It microbenched it and their solution actually faster.

If you have a golden hammer, every problem looks like a red thumb.

Lots of respect for replying to a pretty snarky comment and admitting that you were wrong with good humour, if everyone was like this internet comments would be a whole lot better :)

Ah crap, did it come across as snarky? I'm not very good at conveying tone through comments, it was supposed to be mildly poking fun while making a minor nitpick.

It did, at least the way I read it. That might say more about me than it does about you though :)

Being wrong is fantastic, because it means I have learnt something. In fact I recently had to optimize a troublesome loop and got acceptable results (15 minutes down to 2 minutes thanks to branch mispredicts). Given what I saw today I can go back and see if splitting it up will result in any performance gain.

Agreed, well done for replying with good humor. I think HN is getting more and more of these types of exchanges, which is great.

But the whole point is that the so called O(2n) algorithm isn't necessarily slower than a O(n) algorithm if they aren't doing the same operations. Often two fast operations can be done faster than one slow operation.

It doesn't depend on where you work or whether or not it actually is faster. It depends on what terms you are using and you are using Big O notation. 2n =/= n but O(2n) == O(n)

How about this solution? https://gist.github.com/anonymous/6c83894ecee7016a771d