Do all the things like ++ or -- rants, post your own rants, comment on others' rants and build your customized dev avatarSign Up
ceee83851yThis freaking sucks and happens way more often than I'd like to admit.
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
@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.
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 :)
@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(n log n)
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)