6 ms·

I don’t get the fuss about Big O. Back in my algorithms class, it always seemed like one of the simplest things about algorithms to me. For example, I think it’

I don’t get the fuss about Big O. Back in my algorithms class, it always seemed like one of the simplest things about algorithms to me. For example, I think it’s way harder coming up with complex algorithms in the first place. Is that just me or is Big O just something people outside of university never get around to learn even though it’s simple?

xxpor 6y ago
It's a good check on yourself though. Even if you don't know formal big-O, knowing that something that's O(n) will be faster than O(n!) is pretty important. People who don't realize this end up here: https://accidentallyquadratic.tumblr.com/ https://accidentallyquadratic.tumblr.com/ :)
- quickthrower2 6y ago
  The first example in that link is inside a compiler, so if compiler engineers can make mistakes that makes me feel better! I read it and I think it basically comes down to don’t concat strings for intermediate results, do it at the end.
- taeric 6y ago
  Amusingly, it isn't that simple. 5000n will be larger than n! for several n, after all. And it is often worth realizing that often you can shave time for space, but the setup costs aren't zero. Nor do you always have the space to setup. (For fun in this vein, lookup sortation networks.)
- lern_too_spel 6y ago
  I see other people pointing out that it isn't true for small n, but this isn't true for large n either. The article's binary search implementation is O(n!) (and also O(log(n)), among many others). Its linear search is O(n) (and many others). I can find an N large enough such that the binary search will outperform the linear search for any n>N.
  - xxpor 6y ago
    Sure, but that's not really the point. It's more running more code == probably bad for speed. There's obviously a lot of detail there, like time/space tradeoffs, large constants, etc.
    - lern_too_spel 6y ago
      I'm saying that an O(n!) algorithm is not necessarily faster asymptotically than an O(n) algorithm and that saying it is shows a fundamental misunderstanding of the definition. This is regardless of time/space tradeoffs and large constants.
LandR 6y ago
> Is that just me or is Big O just something people outside of university never get around to learn even though it’s simple? I think so. I reckon if I asked any of the developers I work with "what is Big O" I wouldn't expect any of them to know, but maybe I would be pleasantly surprised. No, no I wouldn't. I have seen their code, they definitely don't know what Big O is.
- smabie 6y ago
  Are you sure? I've never worked with professional devs that aren't familiar with the usual algorithms and data structures. Whenever I interview I'm always asked the usual leetcode bullshit. Are there programming jobs that don't ask/require this stuff? I have met a lot of analysts and researchers that code Python for data science that know nothing of big O, but that's to be expected.
  - LandR 6y ago
    Yeah, I've had to explain to professional developers why them using a List was bad for their use case, they didn't know what else you can use apart from a List. I've had to explain what hash maps are. I've had to explain why nested foreach loops are bad. I've seen code where the dev wanted to create a collection of Foo, they didn't know how many Foos would be in the collection so they made an array that was far bigger than they needed. They then added all the items to the Array one by one, then performed a loop which went round the Array starting at the end and on each iteration it would check if the last item was null. They then resized the Array by 1 item to remove the null entry.... The loop did this until it hit an item that wasn't null... This in a language that has List<T> type... They at least had the sense to write a comment saying someone needed to look into this as it was slow for some reason... This wasn't a junior developer either, it was someone with 15+ years experience. This person would have no idea what Big O meant. I've seen nested foreach loops with a database call in the inner loop!
    - smabie 6y ago
      Maybe I'm being harsh, but those developers should all be fired.
packetlost 6y ago
Big O itself is mostly inconsequential, but computational and memory complexity are very important in a lot of areas of software engineering. In other words, it's a good representation of things that are important, not necessarily hard.
crispyambulance 6y ago
I think ultimately it comes down to the fact that many developers, for reasons which are usually out of their control, simply do not have the mathematical background to that makes notions of O of n intuitive or even understandable. Even if they went to a good university, they might have sleep-walked through their calc/analysis courses and then encountered this stuff later in upper level CS, and learned by rote just enough to pass the class. It's because of a lack of focus on fundamentals in undergrad education.
- jimmaswell 6y ago
  The concepts are intuitive without ever having heard of Big O. The notation can help compare algorithms but it's obvious enough cutting the data in half every step is more performant than looping over them all every time, super deep nested loops should be avoided if possible, etc.
- pmiller2 6y ago
  > ...many developers... simply do not have the mathematical background... for reasons which are usually out of their control... > ...sleep-walked through their calc/analysis courses... I think you both identified the problem and shot down your argument in one breath here. Self taught developers can probably be forgiven for not knowing what big O is, right up until the point where someone asks them about it, and they say "what's big O?" After that, nothing prevents anybody from cracking a book or going on the internet to figure it out.
  - ZephyrBlu 6y ago
    100% agree. The concept of Big O is actually pretty simple, so I would expect someone to be able to pick up the basic given a little bit of research.
DabbyDabberson 6y ago
totally agree. big O notation is like super high level that that doesn't require really doing any math.
hervature 6y ago
I think there are phases to this. 1) Not knowing 2) Knowing Big O and thinking it is always important 3) Knowing Big O and realizing constants matter in practice so you stop optimizing prematurely Anyway, that was my evolution. I agree with most of what you say except I think I would change complex algorithm to complex data structure.
- smabie 6y ago
  In fact, with the way that modern CPUs work, big O can be very misleading, especially with small to moderate amounts of data. Performance nowadays is all about memory locality, avoiding pointers, eliminating the need for branches, etc. For example, with Scala simple Arrays outperform most other collections, including Vectors and Lists, even when the big O is bad. Array languages are especially powerful, even though algorithms implemented in them often do a lot of extra work. If you can keep all of your data in L1, it doesn't much matter what big O you have (usually) and the most naive data structures and algorithms will usually outperform fancy pointer chasing stuff in L3 or RAM.
- megameter 6y ago
  There is a 4 and 5. 4) Realizing that there is a Big O around the larger architecture and thinking it is always important 5) Realizing that archecture is determined by the problem space, so addressing the problem itself as directly as possible will converge on optimal Big O Once you've done it over and over for years it becomes more clear how Big O just reflects the assumptions, and fighting it at the terminating point of the specific algorithms and data is a thing to defer until an easy win is needed. The only effort greenfield code deserves for optimization, OTOH, is to quickly review the language's built-in structures, and pick the one that is approximately best. Push the features, then as time permits build profiling mechanisms to find the hotspots as the system gets production data.
  - pmiller2 6y ago
    There's a 6 as well. 6) Realizing that Big O doesn't matter when you can guarantee your data is always small. Maybe this is more like 4.1 or 5.1, but it certainly does come up.
qppo 6y ago
I have the opposite opinion, people focus on Big O too much. Designing for Big O is like designing for scale. For some reason we can recognize that building a system for a billion users doesn't make sense when you have a thousand... meanwhile we're out writing code with std::unordered_map instead of std::vector with fewer than a hundred elements in the table. We need to make a bigger fuss out of the "C" in Big O, teach people how to use a profiler, and teach more about memory layout and how computers actually function - time complexity isn't time of execution. But too many people treat it like that.
- cmckn 6y ago
  Deciding if your code is a bottleneck is definitely important in deciding how much to worry about asymptotic behavior. But in a lot of cases, it's no more complicated to use a set instead of a list, for example. Totally agree though that benchmarking/profiling is the ultimate decider of what is fast.
  - qppo 6y ago
    Sorry if I was unclear, the point I wanted to make was that asymptotic behavior is not something you need to worry about because it's unlikely your program will behave asymptotically.
cmckn 6y ago
> I think it’s way harder coming up with complex algorithms in the first place. As soon as you start utilizing a data structure or calling another function, understanding the asymptotic behavior of each call can be super helpful. For example: public void f(List a, List b) { for(Object o : a) { if(b.contains(a)) { b.remove(a); } } } This might look like O(a), but is O(a*b), because `contains` and `remove` are O(n). I've come across code at work that was quadratic or much worse because of things like this. Whether or not this matters is more of a wash; if these lists only have 10 elements, meh Big O can also be misleading; modern computers may execute some optimal algorithm slower than a less optimal one, because of cache performance or whatever.

xxpor 6y ago

It's a good check on yourself though. Even if you don't know formal big-O, knowing that something that's O(n) will be faster than O(n!) is pretty important. People who don't realize this end up here: https://accidentallyquadratic.tumblr.com/ https://accidentallyquadratic.tumblr.com/ :)

quickthrower2 6y ago
The first example in that link is inside a compiler, so if compiler engineers can make mistakes that makes me feel better! I read it and I think it basically comes down to don’t concat strings for intermediate results, do it at the end.
taeric 6y ago
Amusingly, it isn't that simple. 5000n will be larger than n! for several n, after all. And it is often worth realizing that often you can shave time for space, but the setup costs aren't zero. Nor do you always have the space to setup. (For fun in this vein, lookup sortation networks.)
lern_too_spel 6y ago
I see other people pointing out that it isn't true for small n, but this isn't true for large n either. The article's binary search implementation is O(n!) (and also O(log(n)), among many others). Its linear search is O(n) (and many others). I can find an N large enough such that the binary search will outperform the linear search for any n>N.
- xxpor 6y ago
  Sure, but that's not really the point. It's more running more code == probably bad for speed. There's obviously a lot of detail there, like time/space tradeoffs, large constants, etc.
  - lern_too_spel 6y ago
    I'm saying that an O(n!) algorithm is not necessarily faster asymptotically than an O(n) algorithm and that saying it is shows a fundamental misunderstanding of the definition. This is regardless of time/space tradeoffs and large constants.

LandR 6y ago

> Is that just me or is Big O just something people outside of university never get around to learn even though it’s simple? I think so. I reckon if I asked any of the developers I work with "what is Big O" I wouldn't expect any of them to know, but maybe I would be pleasantly surprised. No, no I wouldn't. I have seen their code, they definitely don't know what Big O is.

smabie 6y ago
Are you sure? I've never worked with professional devs that aren't familiar with the usual algorithms and data structures. Whenever I interview I'm always asked the usual leetcode bullshit. Are there programming jobs that don't ask/require this stuff? I have met a lot of analysts and researchers that code Python for data science that know nothing of big O, but that's to be expected.
- LandR 6y ago
  Yeah, I've had to explain to professional developers why them using a List was bad for their use case, they didn't know what else you can use apart from a List. I've had to explain what hash maps are. I've had to explain why nested foreach loops are bad. I've seen code where the dev wanted to create a collection of Foo, they didn't know how many Foos would be in the collection so they made an array that was far bigger than they needed. They then added all the items to the Array one by one, then performed a loop which went round the Array starting at the end and on each iteration it would check if the last item was null. They then resized the Array by 1 item to remove the null entry.... The loop did this until it hit an item that wasn't null... This in a language that has List<T> type... They at least had the sense to write a comment saying someone needed to look into this as it was slow for some reason... This wasn't a junior developer either, it was someone with 15+ years experience. This person would have no idea what Big O meant. I've seen nested foreach loops with a database call in the inner loop!
  - smabie 6y ago
    Maybe I'm being harsh, but those developers should all be fired.

packetlost 6y ago

Big O itself is mostly inconsequential, but computational and memory complexity are very important in a lot of areas of software engineering. In other words, it's a good representation of things that are important, not necessarily hard.

crispyambulance 6y ago

I think ultimately it comes down to the fact that many developers, for reasons which are usually out of their control, simply do not have the mathematical background to that makes notions of O of n intuitive or even understandable. Even if they went to a good university, they might have sleep-walked through their calc/analysis courses and then encountered this stuff later in upper level CS, and learned by rote just enough to pass the class. It's because of a lack of focus on fundamentals in undergrad education.

jimmaswell 6y ago
The concepts are intuitive without ever having heard of Big O. The notation can help compare algorithms but it's obvious enough cutting the data in half every step is more performant than looping over them all every time, super deep nested loops should be avoided if possible, etc.
pmiller2 6y ago
> ...many developers... simply do not have the mathematical background... for reasons which are usually out of their control... > ...sleep-walked through their calc/analysis courses... I think you both identified the problem and shot down your argument in one breath here. Self taught developers can probably be forgiven for not knowing what big O is, right up until the point where someone asks them about it, and they say "what's big O?" After that, nothing prevents anybody from cracking a book or going on the internet to figure it out.
- ZephyrBlu 6y ago
  100% agree. The concept of Big O is actually pretty simple, so I would expect someone to be able to pick up the basic given a little bit of research.

DabbyDabberson 6y ago

totally agree. big O notation is like super high level that that doesn't require really doing any math.

hervature 6y ago

I think there are phases to this. 1) Not knowing 2) Knowing Big O and thinking it is always important 3) Knowing Big O and realizing constants matter in practice so you stop optimizing prematurely Anyway, that was my evolution. I agree with most of what you say except I think I would change complex algorithm to complex data structure.

smabie 6y ago
In fact, with the way that modern CPUs work, big O can be very misleading, especially with small to moderate amounts of data. Performance nowadays is all about memory locality, avoiding pointers, eliminating the need for branches, etc. For example, with Scala simple Arrays outperform most other collections, including Vectors and Lists, even when the big O is bad. Array languages are especially powerful, even though algorithms implemented in them often do a lot of extra work. If you can keep all of your data in L1, it doesn't much matter what big O you have (usually) and the most naive data structures and algorithms will usually outperform fancy pointer chasing stuff in L3 or RAM.
megameter 6y ago
There is a 4 and 5. 4) Realizing that there is a Big O around the larger architecture and thinking it is always important 5) Realizing that archecture is determined by the problem space, so addressing the problem itself as directly as possible will converge on optimal Big O Once you've done it over and over for years it becomes more clear how Big O just reflects the assumptions, and fighting it at the terminating point of the specific algorithms and data is a thing to defer until an easy win is needed. The only effort greenfield code deserves for optimization, OTOH, is to quickly review the language's built-in structures, and pick the one that is approximately best. Push the features, then as time permits build profiling mechanisms to find the hotspots as the system gets production data.
- pmiller2 6y ago
  There's a 6 as well. 6) Realizing that Big O doesn't matter when you can guarantee your data is always small. Maybe this is more like 4.1 or 5.1, but it certainly does come up.

qppo 6y ago

I have the opposite opinion, people focus on Big O too much. Designing for Big O is like designing for scale. For some reason we can recognize that building a system for a billion users doesn't make sense when you have a thousand... meanwhile we're out writing code with std::unordered_map instead of std::vector with fewer than a hundred elements in the table. We need to make a bigger fuss out of the "C" in Big O, teach people how to use a profiler, and teach more about memory layout and how computers actually function - time complexity isn't time of execution. But too many people treat it like that.

cmckn 6y ago
Deciding if your code is a bottleneck is definitely important in deciding how much to worry about asymptotic behavior. But in a lot of cases, it's no more complicated to use a set instead of a list, for example. Totally agree though that benchmarking/profiling is the ultimate decider of what is fast.
- qppo 6y ago
  Sorry if I was unclear, the point I wanted to make was that asymptotic behavior is not something you need to worry about because it's unlikely your program will behave asymptotically.

cmckn 6y ago

> I think it’s way harder coming up with complex algorithms in the first place. As soon as you start utilizing a data structure or calling another function, understanding the asymptotic behavior of each call can be super helpful. For example: public void f(List a, List b) { for(Object o : a) { if(b.contains(a)) { b.remove(a); } } } This might look like O(a), but is O(a*b), because `contains` and `remove` are O(n). I've come across code at work that was quadratic or much worse because of things like this. Whether or not this matters is more of a wash; if these lists only have 10 elements, meh Big O can also be misleading; modern computers may execute some optimal algorithm slower than a less optimal one, because of cache performance or whatever.