Learn Big-O and stop hacking your way through algorithms
triplebyte.com
triplebyte.com
People 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:
public void f(List a, List b) {
for(Object o : a) {
if(b.contains(a)) {
b.remove(a);
}
}
}
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.
> 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"
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.