Big O Notation – Explained as easily as possible • Hacker News Board

Re: Big O Notation – Explained as easily as possible

#81

Post by ineedasername » Sat, Jan 16, 2021, 9:30 PM UTC

I'll admit I'm a little surprised to see a topic like this get much attention. Have programming courses & curriculums changed so much in the past ~20 years that this isn't simply part of every introduction to the subject?

Yes, the topic of code performance as a whole is more complex than just Big O, but as its own concept it was, in my time (get off my lawn!) pretty effective covered everywhere, and certainly the moment "algorithms" we discussed in any learning material.

Maybe it's just that it goes back to the common topic here on HN that there's a lot more inefficient code nowadays because faster processors & more memory helps to paper over the cracks. But if something like Big O isn't taught as one of the most primitive bits of knowledge in programming then I can't completely that trend either.

Re: Big O Notation – Explained as easily as possible

#82

Post by kevin_thibedeau » Sat, Jan 16, 2021, 9:42 PM UTC

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.

Re: Big O Notation – Explained as easily as possible

#83

Post by sabas123 » Sat, Jan 16, 2021, 9:49 PM UTC

nicoburns wrote: post #12

bjeds wrote: post #7

If you are the kind of person that want to read an article titled "explained as easily as possible", I think you should just avoid saying the phrase "big oh" but instead talk about algorithm runtime more informally, like "quicksort has a worst case quadratic but average case n log n runtime". The risk is otherwise you will shoot yourself in the foot, maybe during an interview or other situation, as Big O is just one…

The problem with that is that informal use of big-o like notation is a lot more intuitive than the fancy language in your explanantion. Most people who can program can grasp the informal meaning of O(n^2) pretty easily. They may not connect the word quadratic to that say concept.

Why wouldn't you be able to just say "worst case n^2?"

Re: Big O Notation – Explained as easily as possible

#84

Post by matttb » Sat, Jan 16, 2021, 9:55 PM UTC

ineedasername wrote: post #81

I'll admit I'm a little surprised to see a topic like this get much attention. Have programming courses & curriculums changed so much in the past ~20 years that this isn't simply part of every introduction to the subject? Yes, the topic of code performance as a whole is more complex than just Big O, but as its own concept it was, in my time (get off my lawn!) pretty effective covered everywhere, and certainly the mom…

Many, many developers did not go to school and have no 'CS' type learning

Re: Big O Notation – Explained as easily as possible

#85

Post by sabas123 » Sat, Jan 16, 2021, 10:00 PM UTC

pmiller2 wrote: post #25

casion wrote: post #18

Earlier quoted context omitted.

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.

Of course "hard" is relative. Because I was writing a HN post and not a "Big-O explainer," I didn't provide you with any of that prerequisite knowledge. But, the amount of prerequisite knowledge one needs to understand this is very, very little, and would easily fit in a digestible web page, provided you have some basic fluency with functions of the real numbers. And, I think that's a reasonable level of prerequisite…

> But, the amount of prerequisite knowledge one needs to understand this is very, very little, and would easily fit in a digestible web page

I'm really not sure on this one. This is easy if you have an idea of: 1. how you can graph things (runtime vs input size) 2. do the same but stretching the function to infinity 3. compare this to some term (which isn't as tangible compared to most algorithms imo),

And this is only for the intuition part. For people that got into programming by doing some UI stuff, I can definitely can see why _a subset of people_ struggle with this.

Re: Big O Notation – Explained as easily as possible

#86

Post by pmiller2 » Sat, Jan 16, 2021, 10:02 PM UTC

aborsy wrote: post #76

pmiller2 wrote: post #39

Earlier quoted context omitted.

One easy way to show that more generally is that if f and g are differentiable, f(x) dominates g(x) iff f'(x) dominates g'(x), by L'Hopital's rule. Details left as an exercise for the reader.

|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?

Re: Big O Notation – Explained as easily as possible

#87

Post by edflsafoiewq » Sat, Jan 16, 2021, 10:02 PM UTC

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…

In most practical cases f=O(g) is the same as saying f/g is bounded.

Re: Big O Notation – Explained as easily as possible

#88

Post by racl101 » Sat, Jan 16, 2021, 10:10 PM UTC

ineedasername wrote: post #81

I'll admit I'm a little surprised to see a topic like this get much attention. Have programming courses & curriculums changed so much in the past ~20 years that this isn't simply part of every introduction to the subject? Yes, the topic of code performance as a whole is more complex than just Big O, but as its own concept it was, in my time (get off my lawn!) pretty effective covered everywhere, and certainly the mom…

I think this might be for the self taught crowd of developers who never formally took Comp Sci, yet, who are also wielding important positions in software development that pay as well if not more than the guys who did take comp sci.

You'd be astounded how big this self taught cohort could be and how much power they wield.

They do their job pretty well, and yet, the basics of computer science is something that they never learned.

I met a senior guy the other day who had never heard of a freaking truth table for fuck's sake.

Re: Big O Notation – Explained as easily as possible

#89

Post by aborsy » Sat, Jan 16, 2021, 10:22 PM UTC

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?

One function could be below another and have arbitrarily derivative. Even if they are both smooth: f(x)=sin(e^x) and g(x)=1.

Re: Big O Notation – Explained as easily as possible

#90

Post by indymike » Sat, Jan 16, 2021, 10:37 PM UTC

bjeds wrote: post #7

If you are the kind of person that want to read an article titled "explained as easily as possible", I think you should just avoid saying the phrase "big oh" but instead talk about algorithm runtime more informally, like "quicksort has a worst case quadratic but average case n log n runtime". The risk is otherwise you will shoot yourself in the foot, maybe during an interview or other situation, as Big O is just one…

I didn't really read that article as being for a developer. I read it and thought, hey, this one would be good to share with a few project managers & business unit managers. Any time people who are not programmers (especially ones we have to work with) start to better understand what we're really doing, it is a good thing. Articles like this are superb for helping them understand that developers do have a disciplined and rigorous way of solving problems.

I do agree with you that these articles do leave a lot of detail and precision out. They tend to give the reader a superficial understanding of the subject... but a superficial understanding may be enough to help.