In this case however of comparing to another linear form, 2n is slower than n. In a real world example a performance minded programmer would never choose to code something that takes 10 seconds when they could do it in 5.

As said by FArekkusu, that's were you're mistaken: you could compare O(2n) to O(n) only if all operations were of the same kind (if that could be possible...), which will never be the case because, unless you code it on purpose, going from one approach to the other you'll (almost) always end up using different tools (dict/set, for example). And then the specific performances of each of these tools will directly impact the actual performances, and possibly invert what your BigO is telling you. And even if there is no "inversion" of the performances, you'll never end up with a factor 2 going from O(n) to O(2n).

especially on a problem that says to optimize for speed.

the actual meaning here is to avoid a O(n²) algo. ;)

cheers

It looks like you don't really understand what you're talking about. Time complexity is not an execution time metric.

In a real world example a performance minded programmer would never choose to code something that takes 10 seconds when they could do it in 5.

Your solution is actually 3.5-4 times slower than this one using Python 3, and 15-25 times slower using Python 2.

Meaning you don't really understand what you're talking about as long as it comes to complexity, my dear... ;)

To find the asymptotic complexity, you can go through coefficients, but since it is an asymptotic complexity you want, you have to simplify and in the end: O(2n)==O(n) So the asymptotic behvior of both approaches is the same, actually.

Now if you're talking about pure performances, I bet the present code will always be faster than the other one, because of the hashing overhead while there are only ever 2 tranversals here (note: yeah, there is hashing here too, but the fact is: sets are way faster than dicts).

ccl: Do never take asymptotic behavior for an actual measurement of the perfs of the code "on the field". It only gives you ideas about the behavior of the performances when the "n" growths, that's all.

EDIT: and look at the fork, if you really wan't something fast. ;)