6 ms·

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

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.

TravHatesMe 7y ago
O(2n) = O(n)
shantly 7y ago
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" :-)
- deleted 7y ago
  [deleted]
- nikanj 7y ago
  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
  - WorldMaker 7y ago
    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.)
stevefan1999 7y ago
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)
- vanderZwan 7y ago
  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.
  - TravHatesMe 7y ago
    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.
    - baddox 7y ago
      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.
  - protomikron 7y ago
    > 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.
naniwaduni 7y ago
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.

TravHatesMe 7y ago

O(2n) = O(n)

shantly 7y ago

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

deleted 7y ago
[deleted]
nikanj 7y ago
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
- WorldMaker 7y ago
  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.)

stevefan1999 7y ago

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)

vanderZwan 7y ago
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.
- TravHatesMe 7y ago
  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.
  - baddox 7y ago
    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.
- protomikron 7y ago
  > 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.

naniwaduni 7y ago

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.