4 ms·

> Big-O assumes all "operations" are equally costly. This is a big misconception about "Big-O". It does not "assume" anything. It's just not what people think

> Big-O assumes all "operations" are equally costly. This is a big misconception about "Big-O". It does not "assume" anything. It's just not what people think it is. It's an asymptotic upper bound on counting something. In sorting algorithms you count the number of comparisons expressed as a function of collection size. In collection insertion algorithms on some underlying data structure, it's counting some not-very-clearly-defined atomic operations that are being executed when inserting an element. Where the assumptions come from is if you start using the notation to give performance comparisons and also start assuming things about Big-O that are just not true. But that has nothing to do with "Big-O". There is a family of symbols, called the Landau symbols, of which Big-O is only one. There is a lot of misuse of the symbol and in many cases what people actually mean is Theta(N) or Omega(N).

whatshisface 4y ago
This is a pattern of discussion I see a lot on HN: "People who believe in X are wrong because A, B, C." "No, X is actually right, because if you know about these obscure parts of X-theory which laypersons never hear about, you will see that it addresses A, B and C." Of course, both these comments are right, because in addition to the fact that X-theory does in fullness address those issues, few people know how it does.
- Jtsummers 4y ago
  This is CS 101 material here, if it's obscure to people in the software industry, that speaks poorly of the industry and who it hires.
  - bluefirebrand 4y ago
    It's stuff that every CS student encounters but probably relatively few people who are self taught or do coding bootcamps will ever encounter. Also probably a part of a course many people snooze through.
    - ironmagma 4y ago
      People who've only done coding bootcamps probably shouldn't sign on to Hacker News and start preaching about how Big O is wrong.
      - bluefirebrand 4y ago
        Sure, but they still get jobs building software is what I mean.
    - cgriswald 4y ago
      I see it mentioned somewhat frequently by learners on 'learn-to-code' platforms when discussing code. Even when thinking about it wrongly, it can useful.
    - mcguire 4y ago
      I don't know when the original article was published, but Jon Bentley's book Programming Pearls (IIRC) contains essentially this same essay (actually, reversing an array) and was published in 1986.
  - tadfisher 4y ago
    Weird, we didn't get into complexity theory until CS 350. Before that we mostly focused on logic, data structures, and languages (with a bit of computing thrown in). This was at Portland State in the late 2000s though.
  - sitkack 4y ago
    It isn't CS 101. You are being overly dismissive and even CS people from top schools get this stuff wrong. The courses that introduce big-O are often the weeder courses, they don't aim to education, they aim to flunk out the people that might be hard to teach so that CS departments can gate keep. When you have top CS researchers having to give talks to remind people that layout matters more than instruction selection, the CS as a whole has focused on the wrong things. https://www.youtube.com/watch?v=7g1Acy5eGbE https://www.youtube.com/watch?v=7g1Acy5eGbE Figure how to build people up, not tear them down.
    - jcranberry 4y ago
      After an introductory programming course, the next course is data structures which will introduce you to Big O.
    - funcDropShadow 4y ago
      > The courses that introduce big-O are often the weeder courses, they don't aim to education, they aim to flunk out the people that might be hard to teach so that CS departments can gate keep. That is an often re-iterated conspiracy theory. In practice nothing could be further from the truth. Professors have nothing to gain from weeding out students. They have to gain by ensuring a certain standard. By the way it is also better for a student to encounter the difficult parts of their subject as early as possible, so that they can decide whether they have chosen their subject wisely. On the other hand, not failing students on fundamentals means complicating advanced subjects even further --- for everybody. At some point in life students have to accept that neither their time in university nor their time in the industry will consist only of externally motivating tiny bites of tasks that are awesome. In order to understand complicated matters, you have to put in the work. Spending hours in the gym is also quite boring, but most people accepts that it is necessary for certain results. I've been involved with undergrad teaching in a University. And the amount of time we spend on finding ways to teach and test better was way more than I could have expected as a student myself. On the other hand I couldn't have imagined the arrogance and sometimes stupidity of first year student claiming to know already what they will need in there career and what not.
- albedoa 4y ago
  How does "both are right" follow from "few people know why one is wrong"?
  - whatshisface 4y ago
    Because by and large, at least in the example, most people who espouse X do neglect A, B and C.
dfee 4y ago
> In collection insertion algorithms on some underlying data structure, it's counting some not-very-clearly-defined atomic operations that are being executed when inserting an element. Nailed it. My frustration is that those words are rarely mentioned, and that atomic isn’t really atomic except in the context of the problem statement and solution.
aeturnum 4y ago
> 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.
ynik 4y ago
Big-O/Theta/etc. are just tools for analyzing functions. But it also matters which function you are analyzing. Typically a program is evaluated in terms of something like the "Random-access machine" where every instruction has a constant cost. There's a bunch of additional assumptions hidden in this machine model! In the real world, the speed of light and the Bekenstein bound conspire to make constant-time random-access to a memory of unlimited size impossible. In practice, a random memory access takes O(sqrt(N)) time. We like to pretend that there's a constant worst-case access time, but that only works out because our machines have a limited amount of memory -- it's not really appropriate for an asymptotic analysis. So complexity theory based on the "Random-access machine" is just measuring a theoretical instruction count that doesn't necessarily correspond to the real-world run-time. There's other models that get closer, e.g. the "cache-oblivious model".
hinkley 4y ago
But it still falls down so quickly that the smart money is on actually paying attention to the Devil (the details). In its own constructed universe, orders of complexity doesn't obey basic physics. Imagine I'm trying to sort a billion unique books alphabetically by content. In order for the books to be unique, m > logn. For many big problems logn < m < sqrt(n) but for a lot of the rest n < m on day one, and stays that way for quite some time. For large objects, an algorithm that avoids comparisons can be faster with real data even if its complexity is n(logn)^2. Where we fuck up is pretending that mathematical operations are O(1) when they are O(logn) on a good day and O(n) on a bad one. + and - are constant if the numbers fit into a single integer. [] is only constant for n < L1 cache size, and even then only if no other tasks are happening. And as I've just described, < and == are not constant time either. We need better math for these sorts of things.

whatshisface 4y ago

This is a pattern of discussion I see a lot on HN: "People who believe in X are wrong because A, B, C." "No, X is actually right, because if you know about these obscure parts of X-theory which laypersons never hear about, you will see that it addresses A, B and C." Of course, both these comments are right, because in addition to the fact that X-theory does in fullness address those issues, few people know how it does.

Jtsummers 4y ago
This is CS 101 material here, if it's obscure to people in the software industry, that speaks poorly of the industry and who it hires.
- bluefirebrand 4y ago
  It's stuff that every CS student encounters but probably relatively few people who are self taught or do coding bootcamps will ever encounter. Also probably a part of a course many people snooze through.
  - ironmagma 4y ago
    People who've only done coding bootcamps probably shouldn't sign on to Hacker News and start preaching about how Big O is wrong.
    - bluefirebrand 4y ago
      Sure, but they still get jobs building software is what I mean.
  - cgriswald 4y ago
    I see it mentioned somewhat frequently by learners on 'learn-to-code' platforms when discussing code. Even when thinking about it wrongly, it can useful.
  - mcguire 4y ago
    I don't know when the original article was published, but Jon Bentley's book Programming Pearls (IIRC) contains essentially this same essay (actually, reversing an array) and was published in 1986.
- tadfisher 4y ago
  Weird, we didn't get into complexity theory until CS 350. Before that we mostly focused on logic, data structures, and languages (with a bit of computing thrown in). This was at Portland State in the late 2000s though.
- sitkack 4y ago
  It isn't CS 101. You are being overly dismissive and even CS people from top schools get this stuff wrong. The courses that introduce big-O are often the weeder courses, they don't aim to education, they aim to flunk out the people that might be hard to teach so that CS departments can gate keep. When you have top CS researchers having to give talks to remind people that layout matters more than instruction selection, the CS as a whole has focused on the wrong things. https://www.youtube.com/watch?v=7g1Acy5eGbE https://www.youtube.com/watch?v=7g1Acy5eGbE Figure how to build people up, not tear them down.
  - jcranberry 4y ago
    After an introductory programming course, the next course is data structures which will introduce you to Big O.
  - funcDropShadow 4y ago
    > The courses that introduce big-O are often the weeder courses, they don't aim to education, they aim to flunk out the people that might be hard to teach so that CS departments can gate keep. That is an often re-iterated conspiracy theory. In practice nothing could be further from the truth. Professors have nothing to gain from weeding out students. They have to gain by ensuring a certain standard. By the way it is also better for a student to encounter the difficult parts of their subject as early as possible, so that they can decide whether they have chosen their subject wisely. On the other hand, not failing students on fundamentals means complicating advanced subjects even further --- for everybody. At some point in life students have to accept that neither their time in university nor their time in the industry will consist only of externally motivating tiny bites of tasks that are awesome. In order to understand complicated matters, you have to put in the work. Spending hours in the gym is also quite boring, but most people accepts that it is necessary for certain results. I've been involved with undergrad teaching in a University. And the amount of time we spend on finding ways to teach and test better was way more than I could have expected as a student myself. On the other hand I couldn't have imagined the arrogance and sometimes stupidity of first year student claiming to know already what they will need in there career and what not.
albedoa 4y ago
How does "both are right" follow from "few people know why one is wrong"?
- whatshisface 4y ago
  Because by and large, at least in the example, most people who espouse X do neglect A, B and C.

dfee 4y ago

> In collection insertion algorithms on some underlying data structure, it's counting some not-very-clearly-defined atomic operations that are being executed when inserting an element. Nailed it. My frustration is that those words are rarely mentioned, and that atomic isn’t really atomic except in the context of the problem statement and solution.

aeturnum 4y ago

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

ynik 4y ago

Big-O/Theta/etc. are just tools for analyzing functions. But it also matters which function you are analyzing. Typically a program is evaluated in terms of something like the "Random-access machine" where every instruction has a constant cost. There's a bunch of additional assumptions hidden in this machine model! In the real world, the speed of light and the Bekenstein bound conspire to make constant-time random-access to a memory of unlimited size impossible. In practice, a random memory access takes O(sqrt(N)) time. We like to pretend that there's a constant worst-case access time, but that only works out because our machines have a limited amount of memory -- it's not really appropriate for an asymptotic analysis. So complexity theory based on the "Random-access machine" is just measuring a theoretical instruction count that doesn't necessarily correspond to the real-world run-time. There's other models that get closer, e.g. the "cache-oblivious model".

hinkley 4y ago

But it still falls down so quickly that the smart money is on actually paying attention to the Devil (the details). In its own constructed universe, orders of complexity doesn't obey basic physics. Imagine I'm trying to sort a billion unique books alphabetically by content. In order for the books to be unique, m > logn. For many big problems logn < m < sqrt(n) but for a lot of the rest n < m on day one, and stays that way for quite some time. For large objects, an algorithm that avoids comparisons can be faster with real data even if its complexity is n(logn)^2. Where we fuck up is pretending that mathematical operations are O(1) when they are O(logn) on a good day and O(n) on a bad one. + and - are constant if the numbers fit into a single integer. [] is only constant for n < L1 cache size, and even then only if no other tasks are happening. And as I've just described, < and == are not constant time either. We need better math for these sorts of things.