3 ms·
> 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 aro
by zamalek 12y ago
> 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.
- samscott 12y ago> 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.
- zamalek 12y agoWell 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.
- almost 12y agoLots 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 :)
- zamalek 12y agoBeing 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.
- eric_bullington 12y agoAgreed, well done for replying with good humor. I think HN is getting more and more of these types of exchanges, which is great.
- samscott 12y agoAh 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.
- almost 12y agoIt did, at least the way I read it. That might say more about me than it does about you though :)
- deleted 12y ago[deleted]
- dagw 12y agoBut 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.
- seanflyon 12y agoIt 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)