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

    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.
Add Comment