7 ms·

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 a

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.

magicalhippo 4y ago
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).
TchoBeer 4y ago
>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.
- inetknght 4y ago
  > 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.
  - erk__ 4y ago
    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.
DoubleFree 4y ago
The quote "Efficiency with algorithms, performance with data structures"[1] is very applicable imo. [1] https://isocpp.org/blog/2014/12/efficiency-with-algorithms-performance-with-data-structures https://isocpp.org/blog/2014/12/efficiency-with-algorithms-p...
- namibj 4y ago
  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
kadoban 4y ago
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 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.
2OEH8eoCRo0 4y ago
> 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.
- bo1024 4y ago
  That's a good way to put it.
- jonny_eh 4y ago
  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.
KptMarchewa 4y ago
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/PerfListener.cc https://github.com/sio2project/sio2jail/blob/master/src/perf...
- renonce 4y ago
  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.
Thomashuet 4y ago
> 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.
- bjourne 4y ago
  No, in Big-O notation the magnitude of positive constant factors is completely irrelevant.
  - mikebenfield 4y ago
    The fact that the magnitude of positive constant factors is irrelevant doesn’t mean it makes any assumptions about the cost of operations.
- dfee 4y ago
  Give me a sufficiently large n and I’ll give you a sufficiently large constant.
  - ericpauley 4y ago
    False. The whole premise of asymptotic complexity is that the constant factor must be finite as n goes to infinity.
    - tialaramex 4y ago
      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.
wildmanx 4y ago
> 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
trgn 4y ago
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.
bo1024 4y ago
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.
LorenPechtel 4y ago
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.)
- bluefirebrand 4y ago
  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. :)
mfost 4y ago
> 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.
- sly010 4y ago
  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 :)
ouid 4y ago
big O assumes no such thing. big O is just an equivalence relation on functions.
- thaumasiotes 4y ago
  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.
devit 4y ago
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.
shubb 4y ago
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.
hinkley 4y ago
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.
viraptor 4y ago
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.

magicalhippo 4y ago

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

TchoBeer 4y ago

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

inetknght 4y ago
> 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.
- erk__ 4y ago
  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.

DoubleFree 4y ago

The quote "Efficiency with algorithms, performance with data structures"[1] is very applicable imo. [1] https://isocpp.org/blog/2014/12/efficiency-with-algorithms-performance-with-data-structures https://isocpp.org/blog/2014/12/efficiency-with-algorithms-p...

namibj 4y ago
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

kadoban 4y ago

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

2OEH8eoCRo0 4y ago

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

bo1024 4y ago
That's a good way to put it.
jonny_eh 4y ago
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.

KptMarchewa 4y ago

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/PerfListener.cc https://github.com/sio2project/sio2jail/blob/master/src/perf...

renonce 4y ago
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.

Thomashuet 4y ago

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

bjourne 4y ago
No, in Big-O notation the magnitude of positive constant factors is completely irrelevant.
- mikebenfield 4y ago
  The fact that the magnitude of positive constant factors is irrelevant doesn’t mean it makes any assumptions about the cost of operations.
dfee 4y ago
Give me a sufficiently large n and I’ll give you a sufficiently large constant.
- ericpauley 4y ago
  False. The whole premise of asymptotic complexity is that the constant factor must be finite as n goes to infinity.
  - tialaramex 4y ago
    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.

wildmanx 4y ago

> 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

trgn 4y ago

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.

bo1024 4y ago

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.

LorenPechtel 4y ago

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

bluefirebrand 4y ago
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. :)

mfost 4y ago

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

sly010 4y ago
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 :)

ouid 4y ago

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

thaumasiotes 4y ago
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.

devit 4y ago

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.

shubb 4y ago

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.

hinkley 4y ago

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.

viraptor 4y ago

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.