3 ms·

> This is a big misconception about "Big-O". It does not "assume" anything. It's just not what people think it is. In my experience, we all spend more of our t

> This is a big misconception about "Big-O". It does not "assume" anything. It's just not what people think it is. In my experience, we all spend more of our time dealing with what people think things are than what they really are. Even if reality tends to pop its head up now and then. I think the root comment is correctly describing "how people talk about Big-O" - even though, as you point out, they are mischaracterizing it. I find this is often a more vexing problem than the underlying performance questions: how do we find good ways to talk about the use (and mis-use) of analysis in a way that produces good tools?

dgb23 4y ago
Not to mention that it is overemphasized in education. Probably because teachers often are somewhat disjointed from practice. Similarly “competitive programming”, A&D and coding puzzles which I find fun but only tangentially useful, will typically completely neglect engineering constraints. The shape, size frequency and variations of data can almost always be at least estimated in the real world, or simply assumed.
- aeturnum 4y ago
  I don't remember my education over-emphasized Big-O too much - I mostly started thinking about it when I was preparing to do interviews at the end of my undergrad education. I suspect there's been a back-and-forth between industry and schools where industry seeks to weed out very weak programmers (i.e. those who fail fizz-buzz, people who write accidentally exponential code) and schools seek to over-prepare against those easy checks. Real assessments of performance go far beyond the depth and breadth of expertise that most students get in undergrad - so it's a fools errand to try and junior engineers about concepts like that. Big-O has a lot of flaws but I get why it seems so useful to all the groups that use it.
  - dgb23 4y ago
    Assessment of performance can be practiced and taught in the small. It’s really just about making decent estimates, testing and some profiling. There’s of course potential mastery here, specific knowledge and tooling, you can dig down almost indefinitely, but the basic motions can be taught with simple projects. You don’t need Google scale to encounter performance problems and potential improvements. I know this because I work on small scale things, and had to learn this kind of thing on the job. I can imagine a ton of educational projects that teach this. Complexity analysis and A&D are very useful when you need them, but they are just two of several tools.
- WorldMaker 4y ago
  Big O-notation is literally "first-order approximation" (in a complex polynomial, take the "first-order term", which most clearly defines asymptotic behavior, and ignore the rest of the terms as details). It's a simple, silly name for an extremely useful (didactic) tool. I don't think it is teaching that has become disjoint from practice, but practice has become disjoint from the teaching: if I say "first-order approximation" out loud, colloquially people understand it to be "a rough estimate" and plan accordingly, but sometimes in practice people hear "Big O notation" and don't think "this is a rough estimate of just a single term in the equation of complexity of the operation". Similarly the term we use is often "N" and "N" could mean anything, and in practice you need to know what "N" you are optimizing for/against. That's where the engineering constraints fit in. It doesn't matter of you pick an algorithm with good Big-O in time (where n represents number of operations, for instance) if your are constrained in space (memory size; cache size; cache locality) and vice versa. Big O notation is an approximation with respect to some function and that n among a selection of choices of different functions/different "ns", that complexity function itself can vary a lot based on your trade-offs. (Which also gets back into Big O is only one such tool, as well. Sometimes you really need to know worst case "Omega notation" and not really Big O notation, if your constraints include lots of worst case things. And so forth.) Estimation isn't "destiny": know what you are estimating, why you are estimating it, and with respect to what constraints you are estimating it. Big O notation is "back of the envelope math" for algorithms. It serves some great uses, especially in practice, but you need to know what you are estimating and why.

dgb23 4y ago

Not to mention that it is overemphasized in education. Probably because teachers often are somewhat disjointed from practice. Similarly “competitive programming”, A&D and coding puzzles which I find fun but only tangentially useful, will typically completely neglect engineering constraints. The shape, size frequency and variations of data can almost always be at least estimated in the real world, or simply assumed.

aeturnum 4y ago
I don't remember my education over-emphasized Big-O too much - I mostly started thinking about it when I was preparing to do interviews at the end of my undergrad education. I suspect there's been a back-and-forth between industry and schools where industry seeks to weed out very weak programmers (i.e. those who fail fizz-buzz, people who write accidentally exponential code) and schools seek to over-prepare against those easy checks. Real assessments of performance go far beyond the depth and breadth of expertise that most students get in undergrad - so it's a fools errand to try and junior engineers about concepts like that. Big-O has a lot of flaws but I get why it seems so useful to all the groups that use it.
- dgb23 4y ago
  Assessment of performance can be practiced and taught in the small. It’s really just about making decent estimates, testing and some profiling. There’s of course potential mastery here, specific knowledge and tooling, you can dig down almost indefinitely, but the basic motions can be taught with simple projects. You don’t need Google scale to encounter performance problems and potential improvements. I know this because I work on small scale things, and had to learn this kind of thing on the job. I can imagine a ton of educational projects that teach this. Complexity analysis and A&D are very useful when you need them, but they are just two of several tools.
WorldMaker 4y ago
Big O-notation is literally "first-order approximation" (in a complex polynomial, take the "first-order term", which most clearly defines asymptotic behavior, and ignore the rest of the terms as details). It's a simple, silly name for an extremely useful (didactic) tool. I don't think it is teaching that has become disjoint from practice, but practice has become disjoint from the teaching: if I say "first-order approximation" out loud, colloquially people understand it to be "a rough estimate" and plan accordingly, but sometimes in practice people hear "Big O notation" and don't think "this is a rough estimate of just a single term in the equation of complexity of the operation". Similarly the term we use is often "N" and "N" could mean anything, and in practice you need to know what "N" you are optimizing for/against. That's where the engineering constraints fit in. It doesn't matter of you pick an algorithm with good Big-O in time (where n represents number of operations, for instance) if your are constrained in space (memory size; cache size; cache locality) and vice versa. Big O notation is an approximation with respect to some function and that n among a selection of choices of different functions/different "ns", that complexity function itself can vary a lot based on your trade-offs. (Which also gets back into Big O is only one such tool, as well. Sometimes you really need to know worst case "Omega notation" and not really Big O notation, if your constraints include lots of worst case things. And so forth.) Estimation isn't "destiny": know what you are estimating, why you are estimating it, and with respect to what constraints you are estimating it. Big O notation is "back of the envelope math" for algorithms. It serves some great uses, especially in practice, but you need to know what you are estimating and why.