But after reading the table of contents here, I'm thoroughly convinced that this book is not about that. About halfway through, I gave up trying to count the algorithms it was covering because it seems like it randomly decides it wants to be an AI textbook instead. Its focus on AI is weird; if you've got time for Naïve Bayes classifiers, where's convex hull? Where's simplex [1]? Fast Fourier Transform? Union-find? Constraint satisfaction? Hell, where's quicksort?
Another harbinger of quality: there's a section on "Choosing between MD5 and SHA". If you have an entire section on that in a book published in 2023, something is wrong. Then again, an algorithms book needing to have a section on that topic is itself... o_O-worthy.
[1] Okay, there's a section on linear programming. A section. Which, based on the section headings, seems entirely focused on "here's how to use a linear programming solver" and not anything on the actual algorithm itself. My algorithms textbook has an entire chapter on simplex, with instructions on how to code the algorithm itself.
I haven't read it myself, but Algorithm Design Manual (https://www.amazon.com/Algorithm-Design-Manual-Computer-Scie...) also tends to rank high on recommendation lists, and from looking at its table of contents, it does complement CLRS nicely--there looks to be a better selection of things like constraint satisfication or computational geometry.
And then there’s also some algorithms, like for example topological sorting, that are typically implemented as part of application-specific code, not by use of an existing stock implementation. When you know nothing about implementations, you might not notice that the code you’re writing happens to actually be an instance of a well-known algorithm or data structure.
That said, this particular book is an expensive way to line your birdcage, and it should be an O(1) decision to reject it. Shame that ORA put their name on this trash.
It's trivia, and more often than not it's completely useless trivia.
Big-O complexity refers to asymptotic complexity which is only theoretically met with very large datasets which are already in the realm of a RDBMS. Until that point, performance is far more sensitive to cache locality and other implementation details. This means that all those trivia numbers don't even match with real world data you get from your own performance tests.
So what's the point of wasting time memorizing trivia that doesn't even match real-world observations?
For all the other data structure operations it up. But there’s a lot more to data structures than big-O and implementing it yourself is one way to expose yourself to those details (eg cache locality or other things). Crossing abstraction layers requires an understanding of what’s above and below an abstraction. It’s not trivial to have that knowledge and know how to apply it effectively.
It also is not relegated to RDBMS. It can come up when dealing with as few as 1M elements. For example, look up the Rockstar long loading time bug that applied an n^2 algorithm accidentally to something like a few thousand or hundred thousand elements.
But you seem to be pretty into the ignorance is a virtue mantra so not sure there’s any point in engaging further.
(The other is adding network requests, eg database calls, in loops)
Whether or not developers choose to observe time complexity is orthogonal.
But, okay, let's entertain your random tangent. Such a request is emblematic of junior managers/junior manager hopefuls misguidedly trying to wedge their knowledge into the function of the operation. In reality, you don't want to have to build a team that requires discussion about such matters. You need to define clear performance requirements upfront and let the benchmarks speak for themselves. Even if a function is O(N!), but measures successfully within the needs of the application, good enough.
It is especially important to encode these requirements in benchmarks as it documents for future developers the same requirements, and ensures they stay within them as code gets modified. The reality is that you won't be around forever. Keeping a team that relies on you to ask such questions is a failing on you.
But let's accept, for the sake of discussion, that you have failed your team. One still does not need to remember that kind of information. The function they wrote contains what they need to know, and they can consult the function to ascertain that information as needed – just as you could all by yourself in this scenario. If you like keeping such trivia in active memory, good on ya, but it is never necessary.
Big-o notation can also describe space complexity which is a property of the data structure itself and not the algorithmic operations. What I said was a catch all.
As for trivia, it 100% is when literally ever good data structure documentation says the big-o of that operation (+ a lot more details that can sometimes be more relevant). It’s trivia worth knowing for arrays and hash tables but not worth remembering for the various trees because there’s so many of them and they’re used so infrequently (+ implementation decisions can matter which is why reading docs is more important).
I don’t know what problem domains you are working with but algorithmic complexity is not the most common slow code reason I’ve seen new devs run across because the sane generic defaults tend to be relied on for that exact reason (+ code review by someone with experience will catch obvious problems)
The addendum about network calls in a loop makes it sound like his domain uses some kind of SDK with a bad API design. There are some notorious examples which are known to fool new and uninitiated developers who haven't read the fine print into writing code that looks perfectly reasonable on the surface, but does dumb things under the hood.
My experience with new devs is more towards obsessive concern with respect to time complexity, at least where isn't hidden behind a bad API design, fearing an algorithm with high complexity that when measured under its practical use would be just fine. It can be difficult for new (and even old) developers to grasp just how fast computers actually are.
Said database APIs are typically not unreasonable when the database is running in the same memory space as the application, where latency is unnoticeable, as historically was the case when a lot of these APIs were designed. But, as you know, the model breaks as soon as you find yourself in a high latency environment, like over a network.
So then you get some weird bulk operators bolted onto the system to work around the latency issue, but they don't fit the mental model of the rest of the API designed around the idea of single unit operations. Save catching it in the fine print, they go unnoticed. Indeed, the naive programmer who hasn't yet been burned will not be able to fathom that another developer could design such a bad API and will put faith in the idea that the underlying system will somehow automatically mitigate the problem you describe. And in small scale testing it works fine, so there is no reason to doubt that notion. That is, until it is too late...
The experienced developer has learned to stop trusting other developers and bring a heavy skepticism when using another's API. This is a blessing as it means they (usually) stop making those kinds of mistakes when they encounter a bad API, but it is curse as it means they see no reason to fix the problem. "Why don't the junior devs just know better?!" they say. And so, the cycle repeats.
I’ve worked and led teams in multiple problem domains. Devs not understanding how to optimize to avoid slow time complexity is definitely one of the first nuts you have to crack in a new engineer.
Again, not saying it’s irrelevant and it might be highly relevant in some problem domains. But in general big-O of the common data structures should be memorized with the rest being trivia that should be accessible in the documentation for the data structure (or by looking at the implementation and doing it yourself).
I take it that you didn't bother to read the thread you are replying to? There is no reason why you need to have the time complexity of any given function memorized should someone ask. You can – better yet, they can – read the documentation or, failing that, read the code to answer the question. If you happen to have it on hand, that's great and all, but it is only necessary if the asking party see themselves as a trivia master.
> Devs not understanding how to optimize to avoid slow time complexity is definitely one of the first nuts you have to crack in a new engineer.
You never really crack that nut, no matter how experienced, as many problems have no known faster time complexity solution to provide the 'how'. To begin to try to crack that nut you're going to down the road of researcher, not writing day-to-day software, and even then your research is not guaranteed to yield results.
To keep things more substantial, consider facing issues storing data at your company. Maybe the nature of your data flow causes constant slowness, because your B-Tree indices are being constantly rebalanced on writes. You knew this because you understand how B-Trees work and you also know LSM trees might be a better data structure for your needs.
And so what I mean is that understanding the big blocks you use in high level often requires understanding data structures and algorithms, even though you don’t need to implement them
Whether this is truly fun I guess depends on where you are on the developer spectrum. I’d much rather develop low level libraries than app code so any chance I get is just a great opportunity to dig into the low level stuff.
At this point, I can take a look at the rest of the code and see if there's some specific reason a linked list was chosen, or if it was just that the developer didn't put much thought into it. If there is a reason (order matters, etc), I can consider what other structures might _also_ suit that need, but also give faster lookups. And, because I know of a variety of data structures, how they're implemented, and what their characteristics are; coming up with some initial choices (or starting points) happens fairly rapidly.
So yes, I could get all this done without knowing all that information. But it happens a LOT faster because I know it. I notice the issue faster. I have some starting points for options faster. Etc.
Not having that information would not prevent me from doing my job. But having that information makes me _better_ at my job. Faster, more efficient, safer, etc.
Now: the way I approach an example like this is similar to what you do, but the difference is that I'm merely aware there's a bunch of different containers out there which behave in different ways wrt lookup/add/remove/... and for the vast majority of them I have no clue about the implementation. I don't need such implementation knowledge to realize that another container might be the trick here. I also don't really need that knowledge to decide which container that eventually might be, nor to come to conlusions fast (since you're stressing that): that's a couple of minutes to lookup moreover the final decision stage will be through performance testing anyway, because measuring under actual usage is the only way I'll ever be convinced one is effectively better than the other. That's usually what is going to take time, not picking one out of x. In the extreme it might even be so that I'd first need to write a wrapper to then have a configurable container type just to be able to have people test it under different workload types, etc.
Obviously I've been through this a couple of times and by doing so did become aware of main traits of various containers/algorithms/... and yes that will be somewhat faster in the decision process. Likewise there have been certain domains in which I did dig down all the way to the very bottom and obviously having to sort out problems in that domain will be faster for me. But in the end: for me personally 'x algorithms programmers should know' is useless. Job-dependent perhaps, on the other hand I've seen enough people struggle to come up with actual and practically useful software aspects exactly because they kept on getting lost in implementation details.
I guess for me, it boils down to something like "Given a software developer A, adding more experience to them will generally make then a _better_ software developer; and most of that is the knowledge they gained in that experience". Knowledge makes one a better software developer. And knowing more algorithms and data structures is one form that knowledge can take.
- Take a quick look at the symptoms and code and see if it's obvious
- Take a look at the jstacks and see if there's anything that stands out (lots of code stuck in the same place)
- Take a more thorough look at the code to see if anything stands out
- See if I can reproduce the issue locally
- From here it various wildly
I rarely run a profiler just because it's difficult to put it into place in a production environment (which is generally the only place these issue come into play unless you set up the conditions artificially on a lower environment). That's not to say never; I just try to identify the issue other ways first.
It’s like the Microsoft Word problem. 10% of functionality is used by everyone (eg saving a file, opening a file, changing the font). Those are baseline “everyone should know this”. The remaining 90% is still valuable and used by distinct subsets of customers. If Microsoft started deprecating the long tail of features without careful cohort analysis they’d start losing swathes of customers.
So for the most common operations of the most common structures I’d expect memorization of complexities just because of repetition of use (or deriving/guessing it from first principles cause it’s easy for the most common ones). But there’s much more traits and it would be important to understand that (eg what are the primary drivers of CPU time when accessing a hash map? An array? A linked list?).
In many cases it will be impossible for you to write certain parts of code, or you will end up mashing random libraries together, ending up with a program that works 1000x too slow, instead of just writing a few lines of code that solves the issue.
This is especially true for graphs/BFS/DFS and binary trees/search algorithms.
Also, without training your understanding of basic algorithms, you may be unable to write a lots of code that goes beyond wrapping over basic libraries. Not to mention being able to write the libraries themselves.
I would personally say there is definitely no answer to "what should all programmers know" other than at least one programming language along with its associated tooling and enough about a platform software can run on to deploy it. Beyond that, across the full spectrum of software lifecycle careers, I'd say we've started converging on somewhat of a hodgepodge depending on role and where the standards are coming from. IT technician type careers have various certifications coming from platform providers like Cisco, Redhat, and Microsoft, and industry groups like CompTIA. Corporate security gets things like CISSP. If you go to a university, majors in computer science will give you what we expect academics in the subject to know before they can run labs or teach, and software engineering majors some idea what we might expect team leaders in large software organizations to know about how more general engineering principles and practices get applied specifically to software. These tend to have a lot of commonality in terms of at least being familiar with the basics of operating systems and networking, information security, discrete math, data structures and algorithms, programming language paradigms and constructs, possibly some bit of how compilers and maybe processors work.
Then you get what large and well-known employers expect implicitly from their interview and promotion processes. This seems to have also converged largely on at least including basic common programming language constructs, data structures and algorithms, and possibly some minutiae related to specific languages, toolchains, platforms, ecosystems, and possibly larger principles related to things like distributed systems, databases, how the Internet and web work, depending on the nature of the major product lines.
No single person needs to know all of that, but if you do, you're probably reasonably well-prepared to understand the hows and whys of any well-known or largely-used software system. It definitely doesn't mean your daily life as a developer will ever involve directly using that knowledge any more than a practicing psychiatrist remembers and can recite the exact details of the Krebs cycle. But having to learn it still might help guard a bit against susceptibility to bullshit quackery from drugmakers trying to tell them a miracle cure can do something that is metabolically impossible.
Think about ECS in games - that requires a knowledge of data structure that transcends big-O trait comparison to exploit CPU architecture for drastically better efficiency.
You might ignore memory allocations but the under the hood allocations can be important in some cases to make sure they play friendly. Or understanding cache impact and why using a linked list may not be a great idea. Or when sorting+searching may make more sense than just searching.
The more you know the better able you are to make effective decisions and people who work strictly in abstractions tend to be limited in their ability to solve problems that cross abstractions.
Because:
1: Sometimes you need to choose the algorithm, even if it's implemented for you. (Many languages provide many different kinds of collection types, varying on some small details that appear unimportant, until they are very important to your specific need or use case.)
2: Sometimes knowing details of the algorithm helps you avoid edge cases and other inefficient behavior.
3: Sometimes if you know the algorithm exists, you know what kind of library to search for, instead of reinventing the wheel.