6 ms·
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(
by almost 12y ago
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?
- 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)
- lmartel 12y agoYou'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 =)