Hacker News Reader

Comment by savingGrace | Hacker News Reader

I often see O(n^2) algorithms that can be reduced to O(2n) at the very least. One of the best things I gained from school was the red flag that fires off in my mind any time I see a loop nested in a loop.

View on HN

A little experience gets you that same red flag instinct in a hurry, too.

[EDIT] it also makes you hesitate & second-guess and worry and experiment a bunch when contemplating using a recursive algorithm, which is deeply counterproductive in interviews where the expected behavior is so often "apply recursion, instantly and without hesitation" :-)

Unfortunately interviews seem to be all about dogma, and if you even mention performance you will get dinged for premature optimization.

It’s like a postmodern religion where premature optimization is the cardinal sin, and you are supposed to burn as many cycles as possible to demonstrate that you are of good faith

On the flipside, I've met different sorts of interviewers that ding someone for writing something intentionally unoptimized in the spirit of avoiding premature optimization for algorithmic clarity, because don't they have rote knowledge that "x is faster". Dogma on every side of the fence. (Also, continuing proof that technical interviews will never be objective evaluations of skill.)

you shouldn't call it O(2n), as there is already a constant inside of O(n), because it becomes 0 <= f(x) <= c*2n given a random f(x)

Eh, you're technically correct but when used as a point of relative comparison to an O(n²) algorithm I think there's some merit to it, because it actually gives some sense of constant overhead within the context.

What if the constant were massive? Then the coefficient might not be significant in practise. O(2n) might be worse than O(n+99999999), they both reduce to O(n) though. It is a classification.

Personally I would prefer to use different semantics to express that. It seems big O notation often carries a separate meaning in parlance.

I thought big O notation was about classifying function growth irrespective of the coefficient/constant. Does it not grow at all with respect to n? great you are O(1). Does it grow linearly? cool you are O(n). Logarithmically? Quadratically? In my mind, this kind of analysis aligns with big O notation.

If constant factors are significant in practice and the size of the input is not significant, then big O notation is not the right tool for the analysis, and that's perfectly fine. For instance, we generally don't talk about big O notation when comparing the performance of SSDs and spinning HDs.

Big O notation is for describing how the performance of an algorithm changes as the size of its input changes. If the size of the input is not a significant concern, then it's totally fine to not use big O notation for analyzing the problem.

> Eh, you're technically correct [...]

The best kind of correct. Calling it O(n) then is the best way to express the performance improvement - I think that's the whole point of Big-O notation.

However I agree that for smaller n one should not underestimate the constant factor impact.

The point was that you can often convert nested loops into two loops that are not nested. O(2n) conveys that, O(n) does not.

Actually O(2n) did not convey this for me at all, all it did for me was cause confusion. If this ("turn it into two not nested loops") was indeed intended, I'd suggest to spell it out, not abuse notation

Interesting, I hear people spelling out constants all the time when using the O notation to put emphasis where they want. I guess that's not really as universal as I thought, but I still think it's a good way to express.

It can cause more confusion though, if say you write O(kn), but the oh-notation hides a factor k^3, then it would be better to just write O(n). Or write O_k(n) to signify a hidden dependency on k. Or best of all, just write out k^4 n without any ohs at all.

> If this ("turn it into two not nested loops") was indeed intended, I'd suggest to spell it out, not abuse notation

O(2n) is not an abuse of notation. It's just as well defined as O(n). The fact that O(2n) is a subset of O(n) is a theorem, not part of the definition of the notation.

It's a subset, but also a superset.

Yes? But to replace O(2n) with O(n), you only need that it's a subset.

You have your point.

Yet, we understand exactly what he means. Sometimes it's useful to show an un-reduced intermediate step to facilitate understanding, even if you could reduce it further.

Asymptotically, that's true.

In reality, O(n) and O(2n) can be quite different for small n. As can O(n)+k0 and O(2n)+k1. Or worse, O(n^2)+k2 where sufficiently large k0 and k1 make the quadratic system better because it's k2 constant is so much smaller. Setup time matters.

Nowadays, you rarely have enough elements that the asymptotic behavior is the defining performance characteristic.

O notation is asymptotic by definition. The sentence “O(n) for small n” is completely meaningless. O(n) cannot never be different from O(2n) because they refer to the exact same set of algorithms.

Theoretically yes but practically no. Theoretically Big O notation is defined as a limit that goes to infinity but in practice there's no such thing as infinity and saying that an algorithm's runtime is in O(n) implies certain things about its behaviour for finite n, that's kind of the point. And it's perfectly possible for an algorithm to be defined piecewise on the input size and so saying it has runtime O(n) for small n is a statement that has practical significance.

For a moment I assumed that this was another of those cases where copy-pasting to HN lowered a subscript.

Then my brain asked why you'd want to reduce a quadratic algorithm to exponential.

O(2n) = O(n)

Reply on news.ycombinator.com