Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Big O Notation – Explained as easily as possible

thatcomputerscientist.com

Post reply on HN
Print view View original

161–168 of 168 posts

Re: Big O Notation – Explained as easily as possible

#161

Post by dfdz »

gvx wrote: post #152
dfdz wrote: post #130

Disclaimer: I am very familiar with big O notation and find it intuitive. However, I think the notation \lesssim or f(n) \lesssim g(n) if there is an absolute constant C such that f(n) \le C g(n) the meaning is completely clear and by rearranging an expression it can replace big O notation. For example instead of writing f(n) = g(n) + O(h(n)) you write |f(n) - g(n)| \lesssim h(n) https://math.stackexchange.com/questi…

If I understand correctly, f(n) << g(n) is equivalent to f(n) = o(g(n)), not f(n) = O(g(n)).

It depends on the author/field. In analysis sometimes f(n) Due to this ambiguity, I think the notation

f(n) ~< g(n) or in latex f(n) \lesssim g(n) is more clear

Re: Big O Notation – Explained as easily as possible

#162

Post by kaba0 »

casion wrote: post #18
pmiller2 wrote: post #15

Every one of these "Big-O explainers" says pretty much the same thing: count (or bound) the number of steps, then take the most significant term, and drop the constant associated with it. None of them explain why you take the most significant term or drop constant factors. I get why that is. You need the mathematical definition to demonstrate why that is, and most "Big-O explainers" don't want to assume any significa…

You say it isn't hard, but I have 2 graduate degrees and didn't understand your explanation at all. "Hard" is relative to prerequisite knowledge, which can vary significantly.

A function f(n) is O(g(n)) if the graph of f will be underneath the graph of g(n) for a big enough n. (If we want to be more correct, then I would have to add that if there exists a positive number c, and cg should be above the graph of f)

So f(n):=3n+28 will be O(n^2), because choosing c as 3, for every n greater than or equal 4, 3n^2 will be greater than f(n).

It would help if I could draw some graphs, but hopefully it helps.

Re: Big O Notation – Explained as easily as possible

#163

Post by kaba0 »

kevin_thibedeau wrote: post #82
lrossi wrote: post #24

If you really want to make it easy to understand, make it graphical. That is: benchmark the code, varying the input size, and plot the results. Almost anyone should be able to understand. This might also reveal effects that are not taken into account by Big O notation, as not all algorithms that have the same complexity have the same performance. But I see it as a plus.

It isn't uncommon for algorithms with "worse" algorithmic complexity to perform better than the faster alternative because the constant overhead of setting up the "better" algorithm eats all the performance gains. Sequential search is faster than binary search for short lists. You need to test to see where the crossover happens on your platform.

Not necessarily set-up time, but either constants can reverse the roles, or the fact that CPUs are hardly complex and the model most often used in analyzing algorithms is more simple and doesn’t map too well to things like caches, branch-prediction and the like.

Re: Big O Notation – Explained as easily as possible

#165

Post by KnobbleMcKnees »

codesparkle wrote: post #115

A bad programmer solves their problems inefficiently and a really bad programmer doesn't even know why their solution is inefficient To any beginners reading this: Solving problems inefficiently does not make you a bad programmer. Most of the time, an "inefficient" solution will be good enough, and optimising for performance comes at a cost. So sit back, relax, and enjoy the journey.

I wanted to add something to this from recent personal experience.

I've worked with a few engineers recently who were keen - occasionally insistent - on coming up with an O(n log n) solution, or better, at design stages for a specific project. We were working on different parts of the platform (and in different dev environments) but essentially implementing the same thing.

For the implementation I tried to talk them into going with a simpler implementation that was O(n²) for the initial release, but they were adamant not to.

When it came to writing automated tests for the feature, I became aware of some edge cases that hadn't been considered during the design stages. We had another design meeting, updated the requirements, yadda yadda.

A day or so later I put the changes in for review and had them merged reasonably quickly. I later found out that the other group had to significantly rewrite their algorithm and write new tests from scratch, ultimately leading them to miss out on launching the feature at the same time as ours had been released.

The moral of the story? A good programmer knows _what_ the best algorithm is, but a good engineer knows _when_ a given algorithm is called for. Premature optimisation is, after all, the root of all evil.

I've since updated my version to coincide with their more performant version and rewritten a lot of my tests.

Re: Big O Notation – Explained as easily as possible

#166

Post by andi999 »

pmiller2 wrote: post #86
aborsy wrote: post #76

Earlier quoted context omitted.

|g(x)|<M|f(x)| does not imply |g’(x)|<=C|f’(x)|.

Sure it does, for all functions f and g that we actually care about in the CS context for big-O. Hint: what if f and g are smooth?

probably you meant monotonicity

Re: Big O Notation – Explained as easily as possible

#167

Post by brailsafe »

deburo wrote: post #155
codesparkle wrote: post #115

A bad programmer solves their problems inefficiently and a really bad programmer doesn't even know why their solution is inefficient To any beginners reading this: Solving problems inefficiently does not make you a bad programmer. Most of the time, an "inefficient" solution will be good enough, and optimising for performance comes at a cost. So sit back, relax, and enjoy the journey.

That's a popular sentiment to always cuddle new players in a field, but knowing the performance of your algos is part of the job. Performance comes into play in many scenarios. Your users may not "care", but you might be wasting a lot of their time.

Sometimes it is, a lot of the time it's not, or at least not so much so that you're a bad programmer if you do solve a problem but it's not as efficient as it could be. If there's one thing I've realized over a number of jobs where I tried to do things right, it's that most of the time all the work you do doesn't matter, won't last, and your bosses only care that they can list some feature on the product page. They define good programmer as someone who gets their tickets in on time, and if it matters, they can budget for you to improve it with another one.

It's also totally fine to waste some of your user's time if you first create value for them that they didn't have before. That's the nature of iteration and MVPs

Re: Big O Notation – Explained as easily as possible

#168

Post by WinterHoursTF »

ColFrancis wrote: post #134
WinterHoursTF wrote: post #132

I think calling it big O was a mistake. Saying worst case upper bound isn't too many words and conveys the correct meaning to people with incorrect concepts about what big O means.

Calling it big O is indeed a mistake (especially when you start using it with handwriting, o & O because difficult to distinguish). > Saying worst case upper bound isn't too many words and conveys the correct meaning to people with incorrect concepts about what big O means Tricky thing is, that's not what big O says. It's a statement about the asymptotic growth of a function which you can apply to a worst case. You'd…

I know I was just talking about what people always seem to mean by big O. Also it is what O is applied on most of the time.
Post reply on HN