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

101–110 of 168 posts

Re: Big O Notation – Explained as easily as possible

#101

Post by raegis »

jobbo wrote: post #92
racl101 wrote: post #88

Earlier quoted context omitted.

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 ne…

I was dropped into the tech lead position at my job last year; I started in game design at art college, so having to run and gun has been fascinating. I'd be lying if I said I wasn't scared reading about much of the stuff in this comment section that really should be bread and butter. I'm talking to my boss to see if there's some kind of training program I can pick-up on the side to help me gather what should be the…

A few people have made incorrect mathematical statements in this discussion, so having a math teacher might be useful when learning this stuff. My unsolicited advice: take your time and learn some mathematics you might enjoy. Trust simple mathematical definitions over long-winded "explained as easily as possible" essays.

Mathematicians congratulate each other for simple, elegant definitions (sometimes developed over decades) which make deriving results easy. If you don't understand a definition which requires only a few words, learn some of the background instead of doing 10000 Google searches for the "easiest" explanation.

Here's an example. In physics, a vector is something with a "magnitude" and "direction" and we associate feelings and intuition with this. In mathematics, a vector (in 3-dimensional space) is simply "an ordered triple of real numbers". Many people might find this definition unsatisfying, but it is simple, precise, and lots of USEFUL mathematics is created from it.

Re: Big O Notation – Explained as easily as possible

#103

Post by edflsafoiewq »

Al-Khwarizmi wrote: post #97
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…

I'd say that the = is one of the most annoying abuses of notation that I know of, if not the most. Apart from not symmetric, which is a problem in its own right, for small o and small omega it's not even reflexive, which does not prevent the = users from using it also for those. Which amounts to using an equals sign to highlight how two functions differ . And what do people gain with that? It's not as if a set member…

The notation is from math; the point of it is that you can manipulate it like a normal expression, but it's "anonymous"; o(1) means some function that goes to zero, but we don't bother with a name, just recording the asymptotic behavior.

For example, f'(x) = lim (f(x+h)-f(x))/h can be rewritten with an error term f'(x) = (f(x+h)-f(x))/h + o(1), and then you can manipulate it more freely, say like f(x+h) = f(x) + hf'(x) + o(h). There's no need to drag out a bunch of useless names, each qualified by a set membership, to do this. I mean e(h) in o(1), e2(h) := h e(h) in o(h), etc.

The failure of "reflexivity", eg O(f) = O(f), is because the anonymity hides whether the two O(f)s are referring to the same function (ie. exactly what a name would tell us).

Re: Big O Notation – Explained as easily as possible

#104

Post by analog31 »

I learned a couple of things during a brief teaching stint. First, no matter how much math your students learned in their high school and college courses, you should expect to re-teach the concepts that are needed for your lesson. It needn't be extensive, but your students will thank you for it.

Second, don't introduce more than one hard concept at once. Asymptotes can be reviewed with pure math functions such as polynomials, but that's as far as they got in high school math. Then there are the other "interesting" orders such as log(n) that can be introduced, and you can show graphically why they're useful.

Now you're ready to discuss the order of algorithms.

I'm not a computer scientist, but that's how I learned it, and while I don't remember all of the algorithms today, I still understand the derivations of their orders when I see them.

Re: Big O Notation – Explained as easily as possible

#105

Post by kodah »

I learned to code as a kid and only met mathematicians who consider themselves programmers as an adult.

Some opinion, maybe unpopular:

Big O notation can be quite informally understood by normal people. It is academic people that make it and keep it challenging because it is how they understand the world. This is why interviews have stayed materially gruesome despite loud voices wishing it weren't so. It's the language of the people that rule this industry and you either learn it or leave. That said, we can change it too, if we want.

Re: Big O Notation – Explained as easily as possible

#106

Post by pmiller2 »

sabas123 wrote: post #85
pmiller2 wrote: post #25

Earlier quoted context omitted.

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 on…

Sure, a subset may struggle. That's beside the point. I'm most interested in giving people who, as I mentioned, have a basic fluency with functions of the real numbers the answer to why you drop constant multiples and everything but the most significant term. If I wanted to make sure everybody understood (which isn't even theoretically possible), I'd have to include the better part of a semester-long course in my explanation, and that defeats the purpose of having everything in a digestible format.

Re: Big O Notation – Explained as easily as possible

#107

Post by pmiller2 »

aborsy wrote: post #89
pmiller2 wrote: post #86

Earlier quoted context omitted.

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.

Ah, yes, right. Smoothness alone doesn't do it. Nonetheless, I still maintain that the property holds for all functions that we actually care about when doing analysis of algorithms. In particular, it certainly holds for sums and products of n! e^n, n log n, n, log n, and 1, which covers probably 99.9% of everything I've ever seen inside an O().

Re: Big O Notation – Explained as easily as possible

#108

Post by ncmncm »

Big-O notation was the only thing taught to me in a college (tech) class that I use. Everything else I use, I had already learned; you can pick up everything CS departments teach, just by reading. Engineering wasn't like that.

It was taught so well, by Paul Cull, that it seemed obvious and hardly in need of a name.

But I wish I had a nickel for every time some hotshot thinks that, because they got the right big-O performance, they are done. Where performance matters, big-O is is table stakes. There is typically an order of magnitude or two to be gained from that point.

Re: Big O Notation – Explained as easily as possible

#109

Post by School-Cotton »

sabas123 wrote: post #83
nicoburns wrote: post #12

Earlier quoted context omitted.

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

O(n^2) doesn’t necessarily mean worst case; it could mean average case.

Re: Big O Notation – Explained as easily as possible

#110

Post by Tade0 »

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…

I understood your definition (all in all I had calculus 101) but to me it only describes why that is, it doesn't explain it.

Most Big-O explainers don't assume a mathematical background because to non-mathematicians parsing your definition feels like being told you're in a hot air balloon. They see the what, but they don't understand the why.

Post reply on HN