Hacker News Reader

Comment by SAI_Peregrinus | Hacker News Reader

Big-O notation relies on several simplifying assumptions which are wrong in practice. It's not useless, but it's for analyzing algorithmic complexity, not for analyzing algorithmic performance.

Big-O assumes all "operations" are equally costly. That's not the case on real hardware, and pretty much never has been. Some instructions take more cycles than others.

Big-O assumes that only asymptotic behavior matters, but real-world workloads have finite input sizes.

Etc, etc. An algorithm's complexity is loosely correlated with its performance, but the two are not identical.

View on HN

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

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.

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.

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.

People who've only done coding bootcamps probably shouldn't sign on to Hacker News and start preaching about how Big O is wrong.

Sure, but they still get jobs building software is what I mean.

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.

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.

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.

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

Figure how to build people up, not tear them down.

After an introductory programming course, the next course is data structures which will introduce you to Big O.

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

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

So much to unpack there. Some rhetorical hyperbole, other false dichotomy and we are both arguing from anecdote.

Weeder courses exist and as you even admit, they aren't solely meant to educate. That is the point. Anything that is designed to test students resolve as well as not waste professors time is not designed to educate, it is designed to reduce the size and shape of the student population. I applaud that CS departments are adding more and more courses for non-majors. But lets look at the syllabus for a 10 week quarter for the first UW CS course, Foundations of Computing [1] which also expects the students to layout their homework (proofs) in LaTex. Jesus. This is mostly a hazing ritual. In my 3 minute sampling of Reddit, most CS students rank 311 as the hardest course in the major and it is the first. [2]

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

I never said anything of the sort, you putting words in my mouth.

[1] https://courses.cs.washington.edu/courses/cse311/21sp/

[2] https://www.reddit.com/r/udub/comments/cdb5kp/cse_311_cse_33...

> But lets look at the syllabus for a 10 week quarter for the first UW CS course, Foundations of Computing [1] which also expects the students to layout their homework (proofs) in LaTex.

Your argument might make more sense if 311 were the first CS course, but it's not. You can easily verify that by looking at the course listings which reveals it has a prereq, CSE143, which has a prereq of CSE142. So short of skipping those, it's the third course at the earliest.

https://www.cs.washington.edu/education/courses

You are being overly pedantic and arguing for the sake of arguing. The rhetorical language you are using "might make more sense" and "easily verify" is demeaning and insulting and doesn't add to the discussion.

311 is the first course of the major and is also by the sample of folks in the reddit discussion also the hardest, covering the most advanced material in the shortest amount of time. It is a weeder course for the major. The 100 level classes are open to everyone.

How does "both are right" follow from "few people know why one is wrong"?

Because by and large, at least in the example, most people who espouse X do neglect A, B and C.

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

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

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.

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.

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.

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.

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

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.

> Big-O assumes all "operations" are equally costly. That's not the case on real hardware, and pretty much never has been. Some instructions take more cycles than others.

No, it only assumes that there is a constant factor between the fastest and slowest "operations". It does not matter that one instruction can take a thousand times more cycles than another, if you have n² fast instructions and n slow ones, the running time will still be dominated by the n² fast ones for large n.

> Big-O assumes that only asymptotic behavior matters.

Yes, and this is the only simplification that it does.

Give me a sufficiently large n and I’ll give you a sufficiently large constant.

False. The whole premise of asymptotic complexity is that the constant factor must be finite as n goes to infinity.

Machines don't do infinity. This article isn't about an imaginary computer with an infinitely long paper tape from a thought experiment, it's about a real computer, just like the ones many HN readers work with every day.

As a result k*N can actually be bigger than N^2 when in fact N isn't "an integer" in a mathematical sense but merely a 32-bit machine integer, for example - simply by k being more than 4 billion in that case.

> This article isn't about an imaginary computer with an infinitely long paper tape from a thought experiment, it's about a real computer, just like the ones many HN readers work with every day.

If you're determined to throw out any concepts which technically only apply to theoretical computers with unbounded memory, then go all the way. Your actual physical computer can trivially iterate through all of its possible states in a fixed amount of time. The halting problem is trivially solvable for all programs that your actual physical computer can execute. Your actual physical computer isn't even Turing complete.

> Your actual physical computer can trivially iterate through all of its possible states in a fixed amount of time.

Nope. You're in an imaginary world again. This universe will cease to support computation a long time before it would be possible for the computer to try all possible states.

Sure, but that's like saying that your computer could experience power outages or hardware failures at any time. That's true, but we don't normally consider those as limitations to the computational capabilities of your computer.

It's a difference in kind. The computer could experience a power outage, it could experience a hardware failure, but regardless it and all other real computers will cease to operate long before it would be able to explore all possible states.

I don’t think it’s a difference in kind. Given some specific physical computer, how would you determine an n such that n states are iterable on that computer but n+1 states are not iterable due to the universe’s ability to support computation?

Algorithms and programs are different things. An implementation of the algorithm is called a program. Big-O is used for comparing of algorithms. An algorithm can be implemented in different ways. Performance of the program can be measured precisely. Different implementations of the same algorithm will have different performance. When precise information is available, assumptions are useless. When precise information is not available, at design stage, assumptions are used to compare different algorithms.

If N is a 32-bit machine integer, then O(N^2) is actually O(1)

I think that makes sense only for smaller n. At some point your "sufficiently large constant" will need to essentially be computed from the "worse big-O" algorithm to slow the "better big-O" algorithm down enough. E.g. making an O(N) as slow as an O(N^2) algorithm would require a sufficiently large constant roughly equivalent to N^2, at which point you really just have turned the O(N) into O(N^2) in practice.

See also the "galactic" algorithms: https://en.m.wikipedia.org/wiki/Galactic_algorithm

Smaller N happens a lot in the real world. Sequential search can beat binary search for sufficiently small N despite being the "worse" choice.

Because in Software Engineering, layout matters. Computing Machines don't care about asymptotic behavior.

There is something of a bounded limit on how long a single operation could possibly take, assuming your hardware isn't just plain faulty.

Yes, for the purposes of Big O, we define operations such that they aren't simply 1:1 instructions to the hardware, but they should be basic commands offered by your programming language.

If the basic commands in your language are taking extremely high bounded amounts of time, that's a sign your programming language is extremely poorly optimized, not that Big O isn't useful.

A read that hits the network could take a pretty long time.

That's why, when dealing with network algorithms, you analyze the IO complexity in addition to time complexity.

The idea behind Big-O notation is how the time generally varies as you increase the number of items for a given algorithm on a given data structure/data set. That is if you plot a graph `y=f(x)` where `f(x)` is the time taken to perform that operation and x is the number of items you are performing it on. You can then match that resulting curve to a polynomial or other mathematical expression, and Big-O is the dominant term in that expression without any associated scale factors (e.g. for 6x^3 + 2x^2 + 7 you have an O(n^3) algorithm).

Sure, you can choose a large constant such that numerically it is equal to or smaller than O(n^2) for a given n, but as you vary n then O(1) should approximate a flat `y=N` line, while O(n^2) should approximate a parabola and would result in values larger and smaller than N as you vary it.

If the large number you give me depends on the n that I gave you, then what you gave me isn't a constant.

That's not how constants work in mathematics. You have to give the constant first and cannot change it later. That is what it means for a quantity to be constant.

No, in Big-O notation the magnitude of positive constant factors is completely irrelevant.

The fact that the magnitude of positive constant factors is irrelevant doesn’t mean it makes any assumptions about the cost of operations.

>Big-O assumes all "operations" are equally costly. That's not the case on real hardware, and pretty much never has been

Assuming that operations take a linear amount of time (i.e. multiplying three times takes three times as long as multiplying once) this won't affect the asymptotic behavior.

>Big-O assumes that only asymptotic behavior matters, but real-world workloads have finite input sizes.

This is definitely something to keep in mind when analyzing algorithms, but that does not imply asymptotic complexity is not useful when analyzing performance. There are other measures (e.g. how an algorithm performs on a random small input, or maybe your domain is restricted somewhat) and sometimes those measures areore useful than big O, but big O remains useful, it just is not the end all be all.

> Assuming that operations take a linear amount of time (i.e. multiplying three times takes three times as long as multiplying once) this won't affect the asymptotic behavior.

This assumption is demonstrably broken if the first multiplication is a cache miss but the other multiplications then aren't -- an easy example is when the other two multiplications have data on the same cache line as the first multiplication's data.

That is probably a reason big-O is used, the big-O definition which says that they most be upper-bounded by a linear multiplier. So even if the second and third multiplication is faster it will not change the asymptotic behavior.

You're free to use other compuational models in algorithm analysis, which define what costs you're assigning to which operations. If you use big-O on top, then the actual numbers won't matter, but which operations you count certainly do.

For example you could count only non-cached memory accesses on a particular model cpu. See "Idealized Cache Model" from https://en.m.wikipedia.org/wiki/Cache-oblivious_algorithm for example.

This is part of algorithms analysis that a lot of developers skip: these are just tools, there's many models available to use with them, or if you want to, just use wall-clock, with all of the pain that comes with that.

> it's for analyzing algorithmic complexity, not for analyzing algorithmic performance.

Everyone seems to forget this. It's more a measure of how an algorithm will scale rather than performance.

That's a good way to put it.

It's still useful for comparing potential performance of algorithms with different O(x).

e.g. an O(n) algorithm will most likely outperform an O(n^2) algorithm, but two different O(n) algorithms can still perform quite differently.

But you're right, it's meant for comparing scaling.

Indeed. I do think knowing about big-O and keeping it in mind is important though.

Yes this loop is fast now with my 1000 items, but what if the input grows to 100000 or more?

Keeping it in mind can also help you avoid accidentally writing O(n^2) loops or worse. More than once I've been unsure about the complexity of a library call, so I check the code and it's say O(n) rather than O(1), potentially turning my own O(n) into a O(n^2).

At the extreme ends, there are two kinds of slow computations.

1. A small computation that you perform many, many times.

2. A very, very large computation.

For #2, big-O can still generally tell most of the story. (Example: 100 insertions in the middle of a list with a billion elements.) For #1, big-O almost irrelevant, and benchmarking is key. (Example: a billion insertions into the middle of length-100 lists.) So knowing which situation you're in is important.

The quote "Efficiency with algorithms, performance with data structures"[1] is very applicable imo.

[1] https://isocpp.org/blog/2014/12/efficiency-with-algorithms-p...

Actually, things like merge-join can benefit from the hierarchical aspect of something like a Btree, making not only the individual accesses/seeks more efficient, but also saving more in the first place

Some algorithmic competitions (eg. Polish Olympiad in Informatics) go even further, and judge programs not on execution time, but on executed instruction count, effectively emulating processor with very large amount of RAM.

https://github.com/sio2project/sio2jail/blob/master/src/perf...

A practical example that counts instructions is EVM. Gas usage is counted deterministically to limit computation overhead, and smart contracts are designed to optimize away every unit of gas since they cost real money.

> Big-O assumes that only asymptotic behavior matters, but real-world workloads have finite input sizes

Well I did have a CS teacher that said that O(log n) is basically O(1) because in practice, n usually will fit it in a 32bit and log n then is 32 at most :D

It might have been said in jest in part but really it's not that far fetched.

And similarly, very few algorithms are better than O(n), because something as simple as adding 2 numbers can be O(n) where n is the size of the number in bits :)

Agreed. I'd go a step further, there's a real-world heuristic that this implies.

Initially, prefer to task CPU over memory allocation. Crufty allocation generally will always have a real negative impact felt by the end-user. A low memory footprint is always a win, while going for a (theoretical) fast running time may be effort wasted.

A bunch of operations classically represented as O(1) are O(logn) with step functions. They are only constant time for ranges of values, and eventually the response curve smoothes back out into a logn line.

And the usual argument is, "well, it's understood..." which is a terrible argument because the whole notion of ignoring constant factor C is that it's supposed to go to the noise floor as n approaches infinity. So if you're going to claim that we didn't mean n approaches infinity, we meant "n fits into a CPU word and the data set fits into memory" then you're trying to have it both ways and that's pure nonsense.

Sort of.

As you go up the scale the Big-O values are almost always dominant. It's very rare to see a situation where you would choose the algorithm with the higher value.

However, when two algorithms have the same Big-O there can still be a big difference in performance, especially in the face of how a cache influences things.

(There are cases where the memory accesses are so important that they can make the "bad" approach better. A while back I did some time testing and found the Sieve of Eratosthenes inferior to brute force because of all the cache misses.)

At a certain point your best bet is really to profile the two approaches to see which performs better.

But if you are starting out with nothing built and only have time to write one, you can't really go wrong by going with the one with the better Big O. If it's the same, coin toss I guess. :)

You're assigning agency to a notation, which is not very productive. Big-O doesn't "assume" anything, doesn't depend on what "matters", or try to achieve anything. It's well defined and you need to understand what Big-O is to understand its result.

If you want a better overview of algorithms for practical reasons, you can use o(), O(), average case and ammortised complexity, or just provide histograms of runtimes for algorithms you're comparing.

big O assumes no such thing. big O is just an equivalence relation on functions.

But big-O is not an equivalence relation on functions, because it isn't an equivalence relation. A big-O relationship is not symmetric: if f(x) = x² and g(x) = x³, you can see immediately that f(x) = O( g(x) ), but it is not true that g(x) = O( f(x) )

Big-O is a statement about the limit of a function as the input goes to infinity. f(x) = O( g(x) ) is the statement that the limit (f/g)(x) exists as x goes to infinity. f(x) = o( g(x) ) is the stronger statement that the same limit exists and is equal to zero.

In practice the difference between constant factors is usually between 10 and 10^4, while input size can go up to 10^10 and more, so factors of sqrt(n) or higher will usually always matter, while factors of log(n) or lower will often not matter, and factors in between will depend.

Be careful - many people here hang an entire identity on their high status, high paid jobs which were earned by memorising the answers to theoretical algorithms questions. It is important to their self worth that that stuff is relevant to the real world.

You'll get a similar reaction to if you try to show people who won money on crypto art or tesla that they are lucky early members of a pyramid scheme.

Reply on news.ycombinator.com