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?
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.
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.
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.)
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.
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.
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.
> 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.
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!
Maybe there’s a need here for a one-day class that teaches these concepts, and then managers can send their experienced (but ignorant of Big O) devs there rather than being fired?
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.
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.
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.
> ...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.
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.
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.
100%. in reality you're more often than not well nigh of asymptotic, so it's not always obvious what implementation is preferable. there are situations where you have a crossover in runtime between two implementations. if the n for your practical use case is less than than critical value, the asymptotically optimal solution is suboptimal.
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.
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.
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.
> 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.
is this an appropriate place to ask if triplebyte ever plans on staffing more interviewers? I'm tired of getting marketing emails telling me to schedule my interview when there hasn't been availability for coming up on 9 months now. Might make more sense to hire interviewers, rather than blog writers.
Oh look another Triplebyte article that makes to the top of HN while also being completely devoid of useful information -- and, in fact, quite wrong.
> The truth is, Big-O is just the name of the notation used to describe how efficient an algorithm is.
The truth is that this is absolutely unequivocally unabashedly WRONG. Big O (there's no dash, first of all), describes the behavior of some function f as f tends to infinity (but we can actually look at Big O when f approaches arbitrary values, as well). The "O" in Big O references the function order of the limiting function --, e.g. logarithmic, quadratic, cubic, and so on. If you're going to make a hubbub about truly understanding Big O, at least get the math bits right.
> Learning about how they work without understanding the associated implications of time and space complexity misses the point.
Some fresh grad probably wouldn't realize how laughable this claim really is, but seasoned developers do. 99.9% of times you don't care (or even understand; some are quite hairy) about the (micro-)optimizations found inside standard library functions or data structures.
> It's like memorizing dates in roman history without having heard of Julius Caesar...
Yeesh, capitalize "Roman" please. What a low-quality trash-heap of an article.
> And on top of making learning easier, understanding the point of Big-O (and algorithms in general) will seriously help you avoid mistakes in interviews.
Ah yeah, here we go. Finally, we get to the only practical use case of Big O unless you're a CS PhD: getting through interviews.
Overall, this is a zero effort pseudo-marketing blog post that hasn't been researched, edited, or proof-read. It's all so Triplebyte can make the top of HN, get a bit of traffic, and keep reinforcing horrible interviewing practices that don't work. I swear, one of these days I'm going to write a book about how to actually do a good job of interviewing software engineers.
>> I swear, one of these days I'm going to write a book about how to actually do a good job of interviewing software engineers.
Same, except I can fit mine in a blog post. Tripplebyte got on here a few years ago and wanted people to conduct technical interviews so I started to sign up / apply. Then they wanted me to take their javascript test... I've never written js, nor would that have much if any bearing on my ability to interview software candidates.
NIST disagrees [1]. It is in common use both with and without the dash in both CS and math. Looking around in various books I downloaded from Springer when they made nearly 400 books free for a couple of months in response to COVID, I see several that include the dash.
Laczkovich and SoS, "Real Analysis"
de Berg, Cheong, van Kerveld, and Overmars, "Computational Geometry"
Lee and Hubbard, "Data Structures and Algorithms with Python"
Borthwick, "Introduction to Partial Differential Equations"
Paar and Pelzl, "Understanding Cryptography"
Haubold an Borsch-Haubold, "Bioinformatics for Evolutionary Biologists"
I end up doing hand-wavey explanation of things that abuses the terms of Big O because then it suddenly seems like its a real, valid argument, but what I really wish I could just say it how it is and have people understand and respond correctly:
"If the time the server spends is proportional to number of requests coming in, and the number of requests coming in is proportional to user engagement, and we expect user engagement to grow over time by a rate also proportional to user engagement -- but the amount of server time we have available to serve requests is constant (there's no designed solution to scale horizontally) then we have a problem."
Not a surprise problem that suddenly appears on the day where we run out of resources, but a problem to solve today, right now, because we are already over-committed by the nature of this design, and not a problem we can solve by making the single node any bigger to start out with...
But many are seemingly strongly conditioned by education (whether that includes CS or not) to only pull out certain techniques when a problem presents itself in a pre-packaged familiar way, so if I whip out Big O, folks are suddenly able to see that they're on the losing side of a bet pitting a flat line against a curve.
39 comments
[ 5.2 ms ] story [ 118 ms ] threadPeople who don't realize this end up here: https://accidentallyquadratic.tumblr.com/ :)
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.)
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.
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.
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!
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.
> ...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.
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.
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.
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.
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.
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.
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:
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, mehBig O can also be misleading; modern computers may execute some optimal algorithm slower than a less optimal one, because of cache performance or whatever.
> The truth is, Big-O is just the name of the notation used to describe how efficient an algorithm is.
The truth is that this is absolutely unequivocally unabashedly WRONG. Big O (there's no dash, first of all), describes the behavior of some function f as f tends to infinity (but we can actually look at Big O when f approaches arbitrary values, as well). The "O" in Big O references the function order of the limiting function --, e.g. logarithmic, quadratic, cubic, and so on. If you're going to make a hubbub about truly understanding Big O, at least get the math bits right.
> Learning about how they work without understanding the associated implications of time and space complexity misses the point.
Some fresh grad probably wouldn't realize how laughable this claim really is, but seasoned developers do. 99.9% of times you don't care (or even understand; some are quite hairy) about the (micro-)optimizations found inside standard library functions or data structures.
> It's like memorizing dates in roman history without having heard of Julius Caesar...
Yeesh, capitalize "Roman" please. What a low-quality trash-heap of an article.
> And on top of making learning easier, understanding the point of Big-O (and algorithms in general) will seriously help you avoid mistakes in interviews.
Ah yeah, here we go. Finally, we get to the only practical use case of Big O unless you're a CS PhD: getting through interviews.
Overall, this is a zero effort pseudo-marketing blog post that hasn't been researched, edited, or proof-read. It's all so Triplebyte can make the top of HN, get a bit of traffic, and keep reinforcing horrible interviewing practices that don't work. I swear, one of these days I'm going to write a book about how to actually do a good job of interviewing software engineers.
Same, except I can fit mine in a blog post. Tripplebyte got on here a few years ago and wanted people to conduct technical interviews so I started to sign up / apply. Then they wanted me to take their javascript test... I've never written js, nor would that have much if any bearing on my ability to interview software candidates.
NIST disagrees [1]. It is in common use both with and without the dash in both CS and math. Looking around in various books I downloaded from Springer when they made nearly 400 books free for a couple of months in response to COVID, I see several that include the dash.
Laczkovich and SoS, "Real Analysis"
de Berg, Cheong, van Kerveld, and Overmars, "Computational Geometry"
Lee and Hubbard, "Data Structures and Algorithms with Python"
Borthwick, "Introduction to Partial Differential Equations"
Paar and Pelzl, "Understanding Cryptography"
Haubold an Borsch-Haubold, "Bioinformatics for Evolutionary Biologists"
[1] https://xlinux.nist.gov/dads/HTML/bigOnotation.html
I'd say whoever wrote the NIST article is wrong because there's absolutely no grammatical reason to hyphenate, but that's a minor nit.
"If the time the server spends is proportional to number of requests coming in, and the number of requests coming in is proportional to user engagement, and we expect user engagement to grow over time by a rate also proportional to user engagement -- but the amount of server time we have available to serve requests is constant (there's no designed solution to scale horizontally) then we have a problem."
Not a surprise problem that suddenly appears on the day where we run out of resources, but a problem to solve today, right now, because we are already over-committed by the nature of this design, and not a problem we can solve by making the single node any bigger to start out with...
But many are seemingly strongly conditioned by education (whether that includes CS or not) to only pull out certain techniques when a problem presents itself in a pre-packaged familiar way, so if I whip out Big O, folks are suddenly able to see that they're on the losing side of a bet pitting a flat line against a curve.