Three days thinking of a solution to a problem in HackerRank...

Came up with a very elegant O(n+m) solution... failing several test cases...

Check here, there, over there. Everything seems flawless...

Re-read the problem statement letter by letter. There it is, I misread the requirement. FML

This freaking sucks and happens way more often than I'd like to admit.

@rsync for simple algorithms is not that hard. You just have to follow some rules and know some cases. Basically it's just practice.

But I didn't paid a lot of attention in class either. I had to re-study it again a few years later.

@rsync I do the math and make exact bigO expressions, and then get laughed at when I show them to others. I really should just simplify them to e.g. O(3n), but that isn't right at all!

(I don't remember any good examples right off [sorry], but they look like algebra)

@Root well, actually when expressing time (or space) complexity of an algorithm, the common recommendation is to simplify the expression.

For example O(3n + 4) should be simplified to O(n) because it's linear time.

Big O is basically a way to describe how fast the execution time (or space) of an algorithm grows regarding the input.

@grayfox I've always seen that as an oversimplification. 3n != n

Simplifying them in such a way leaves us with only a few possible "measurements":
> O(1)
> O(n)
> O(n log n)
> O(n^x)

Even O(constant) would be reduced to O(1), despite that being quite wrong. 1000 clocks != 1 clock. Even using Fermi estimation that's very wrong.

And what about very precise measurements like O(3n + n log n)? How would you simplify that?

@Root I agree with you on that BUT based on the literature, big O is used in order to compare the efficiency of solutions.

So if your implementation of merge sort is O(n log n + 5000) and a bubble sort is O(n^2) the '5000' doesn't make any difference so it's basically O(n log n) vs O(n^2) and if you come up with RootSort which is O(1000*n) the 1000 won't make any difference compared to a n^2, it will always be better because is linear.

@Root Practically, the rules are often defined as: "If f(x) is a sum of several terms, if there is one with largest growth rate, it can be kept, and all others omitted. If f(x) is a product of several factors, any constants (terms in the product that do not depend on x) can be omitted."

I disagree with this, because the formal big O definition prohibits omission of factors. While the slower growing TERMS (+) do not affect the overall growth rate at larger scales, FACTORS (*) absolutely do.

O(3n) => O(3n), not O(n)

O(2n^2 + 3n + 6) => O(2n^2), not O(n^2)

@grayfox fair enough. Constants don't really change much. But my approach does help if you know the size of `n`

Edit: @bittersweet said it very well.