Hacker News Reader

Comment by zamalek | Hacker News Reader

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

View on HN

> 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 :)

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.

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 :)

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)

Reply on news.ycombinator.com