29
grayfox
1y

# 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

• 9
This freaking sucks and happens way more often than I'd like to admit.
• 6
yeah it sucks, happens often to me too. Except I am more into codesignal than hacker rank.

I should have paid more attention in algo class because I have absolutely no idea how to classify algo's I just say O(nlogn) :D
• 1
@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.
• 1
@antorqs

Princeton has an amazing algo class online that I started. Probably need to finish it eventually so I too can know the specifics of big O notation :)
• 1
@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)
• 1
@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.
• 2
@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?
• 1
@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.
• 3
@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)
• 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.