In every interview I have been in, I have been quizzed on mathematical analysis of complexity, including big-O notation.
How relevant is big-O analysis to development in industry? How often do you really use it, and how necessary is it to have a honed mindset for the problem?
My question is, how relevant is this test to development in industry?
A solid understanding of computational complexity theory (e.g. big O notation) is essential to design scalable algorithms, applications and systems. Since scalability is highly relevant to computing in industry, big O notation is too.
How often do you reeeally use it, and how necessary is it to have a honed mindset for the problem?
Depends what you mean by "reeeally use it". On the one hand, I never do formal proofs of computational complexity for the software I write. On the other hand, most days I have to deal with applications where scalability is a potential concern, and design decisions include selection of (for example) appropriate collection types based on their complexity characteristics.
(I don't know whether it is possible to consistently implement scalable systems without a solid understanding of complexity theory. I would be inclined to think that it is not.)
The reason for this is because it indicates scalability.
A process that is O(n^2) will scale worse than one that is O(n log n), but better than one in O(n^3) or even O(n!).
If you do not know the differences and when they apply, you are less suited for choosing the right implementations of functionality, as well as extrapolating test performance into production performance.
EDIT: A comparison of 48n with n^3 from http://www.codinghorror.com/blog/2007/09/everything-is-fast-for-small-n.html (which in turn is from Programming Pearls)
O(log Customers) dB.
It depends on what your are doing.
For web developers (such as me) this usually matters a lot. You want web apps to scale. If your app has a bottleneck that scales with O(n^2), and you think this is just fine, because your server can handle 1000 simultaneous users, it seems you needn't care. The thing is, to handle just twice as many (which is reasonably probable to happen just over night), you'll be needing 4 times the computational power. Ideally you want web apps to scale at O(n), because hardware is cheap at a sensible constant user/server ratio.
Generally in apps, where you have 100000s of objects, big O will come and eat you. You are enourmously vulnerable to peaks. For example, I am currently working on a 3D game, which is an app that handles loads of data. Apart from the rendering, you have collision checking, navigation etc. You can't afford just going the obvious way. You need efficent algorithms, you need a lot of caching so the less efficient ones amortize. And so on.
Of course if what you do is something like making a mobile app by throwing together a GUI in an interface designer, wire that up with some web services and that's it, then you will never have issues with complexity. Because the web services you call already take care of it.
I never actually applied formally the rule in my working life.
However you have to be familiar with that concept, and apply it in an intuitive way every time you design an algorithm.
The rule is:
You should be enough familiar with the O notation to being able to determine, for a given task, if it is required to formally calculate it, or it is just enough to evaluate it intuitively, or if you can just skip it entirely. Just like many other basic mathematical concepts.
Well, maybe a little story enlightens you why it DEFINITELY IS necessary:
In a project I've been working at, there was a program responsible for printing all kind of documents (labels, picking lists etc.) This program consisted of two parts, one reading all the necessary data from the database and writing it into a .ini-style file, and another part that read those files and filled it into the templates. This worked reasonably well for labels and small lists (with only a few fields) but it ran for almost 10 minutes when it had to print a "large" list of ~20 pages. Because accessing these ini-files resulted in O(n²) access times, n being the number of fields to print.
Had the original programmers of this program understood O-notation, they would never have made it that way. Replacing that stupidity with a hashtable made it soooooooo much faster.
Big-O performance is important, but it's been largely internalized.
The Big-O performance of sorting and searching doesn't matter, because people generally use the system-supplied ones, and those will be as good as they can be (given that they need to be generally useful). There are data structures that are more efficient for different things, but those can usually be selected on general principles (and are typically built into modern languages). There is some sense of algorithms that do or do not scale.
The result is that the formal issues rarely come up in practice, but practice is built on the same principles.
IMHO a lot of computer science programs leave many students wandering down there in the weeds. These programs never quite communicate the big picture of what science of computation is all about. The students enter the industry, grappling with how to apply the concepts they have learned, with little insight into how they relate to the real world.
I would say that the heart of science of computation is the ability to reason about computation. And you learn various methods and techniques to do this, and apply them to abstracted problems, that are prototypical primitives found in many real world problems. The trick is to spot these prototypical primitives in the real world, and then reason about things like correctness, complexity, time etc., which, you may agree, are real issues that you need to worry about. Insight into how the parts behave, frequently gives you insight into how the whole behaves. And the same general methods and techniques can also be applied to the whole, just not with the same rigorousness that is afforded to smaller, well abstracted, well defined parts. But in the end, the science of computation, endows you with the ability to make reasonable decisions about how to arrange your computation, with real insight into how it will behave under various conditions.
Memo to self!:
I and many others ask themselves this question regularly.
I think the real reason we ask this is because we have become lazy.
This knowledge will never date or become obsolete. You may not apply it directly on a day to day basis but you will use it subconsciously and it will have a positive affect on your design decisions. One day it may save you or others hours and days of coding.
As more problems are encapsulated by 3rd party libraries and tools and are available to more and more developers, you will need to know this knowledge to distinguish yourself from others and to help solve new problems.
Not really. Basically the only time I ever think about it is when accessing the database. I'll usually look at code and say "That's doing n+1 queries, you should change it to do just 1 or 2"
Because all of my data is being read from a database and shown to the user, I try to minimize the amount of data I'm working with to the point where the difference between a linear and an O(n^2) algorithm is pretty negligible.
If there's a problem, we'll profile and fix it later.
Three questions you put and I think short-form answers could aid the longer arguments given so far.
How relevant is this test to development in industry?
Depends on the industry.
Anywhere where code speed or code space is an issue, it is entirely relevant to the industry involved. Often you need to know how long a routine will take, or how much memory (on/offline) it will require.
How often do you reeeally use it?
Depends on the industry.
If performance and scaling is of little concern to the job at hand, then rarely, only when there is a serious performance shortfall. If you are an engineer for a highly used critical system, every day probably.
How necessary is it to have a honed mindset for the problem?
Entirely necessary.
You may have to use it everyday, or only in dire circumstances; but sometimes it will be needed. Preferably during design before an issue arrives, than desperately profiling a choking system.
I'd say it's very frequent. We don't generally prove something has a particular big-O, but we have internalized the idea, and memorized/become familiar with the big-O guarantees for particular data structures and algorithms, and we pick the fastest ones for a particular use. It helps to have a library that's full of all of the options, like the Java collections library, or the C++ STL. You implicitly and naturally use big-O every day when you choose to use a java.util.HashMap (O(1) lookup) instead of a java.util.TreeMap (O(lg n) lookup) and certainly choosing not to run a linear search across a java.util.LinkedList (O(n) lookup) for something where you don't need sorted access.
When someone chooses a suboptimal implementation and someone who knows better comes along and sees their code, it's a part of our vocabulary to correct them "your implementation takes quadratic time, but we can get this down to n-log-n time by doing it this way instead" as naturally and automatically as we would use the English language to order a pizza.
Map non-concurrent implementations... actually, I use TreeMap when I need to keep the entries sorted by a key. LinkedHashMap when I need to preserve the order of the insertion and HashMap for no such requirement. If the number of entries is less than < 10000, I'd really not care if the lookup is O(logn) or O(1).
Aug 28, 2020 at 22:10
LinkedList compared with ArrayList, but nobody is interested in the fact LinkedList is only useful when you need a List and Deque at the same time (since it implements both interfaces). Otherwise, one should use either ArrayList or ArrayDeque respectively. Knowing interfaces and how it works is important. The average time complexity for n values are to be easily Googled and compared.
Aug 28, 2020 at 22:12
Yes
You may not have to do formal analyses, but at least a gut understanding of the order of algorithm complexity - and how to compare two algorithms around that - is critical if you want to do non-trivial work and have it turn out well.
I've worked on two different systems that seemed fine in early development, but brought the hardware to its knees in production testing, because somebody used an O(n^2) algorithm. And in both cases, the fix was a trivial change to an O(n) algorithm.
It's probably used in places where they are developing APIs for consumption. The C++ STL is one of the few APIs that has complexity restrictions imposed on its algorithms. But for the everyday working programmer/senior programmer/designer/architect it doesn't cross their minds much.
I've not found it that important except to communicate ideas, and I work in performance-critical fields (raytracing, image and mesh processing, particle systems, physics engines, etc) and have had to devise a lot of proprietary algorithms and data structures when working in R&D. In these areas, often a handful of very efficient data structures and algorithms can yield whole new cutting-edge products while yesterday's algorithms make existing products obsolete, so there's always a pursuit of doing things more efficiently. As a caveat though, I've never published any papers on the algorithms I devised. They were all proprietary. If I did, I'd need the aid of a mathematician to formulate proofs and so forth.
Yet in my opinion the amount of computational work per iteration is often of more immediate interest than the scalability of the algorithm unless the algorithm scales really poorly. If someone comes up with a cutting-edge technique for raytracing, I'm more interested in the computational techniques like how they represent and access data than algorithmic complexity because reasonable scalability is already a given in this competitive and innovative scenario. You can't be competitive coming up with algorithms that don't scale.
Of course if you're comparing quadratic complexity to linearithmic, that's a huge difference. But most people in my field are competent enough to avoid applying a quadratic complexity algorithm on an epic input. So scalability is often deeply implied, and the more meaningful and interesting questions become like, "Did you use GPGPU? SIMD? Does it run in parallel? How did you represent the data? Did you reorganize it for cache-friendly access patterns? How much memory does it take? Can it robustly handle this case? Are you deferring certain processing or doing it all in one go?"
Even a linearithmic algorithm can outperform a linear-time algorithm if the former accesses memory in a more optimal pattern, e.g., or is better suited for multithreading and/or SIMD. Sometimes even a linear algorithm can outperform a logarithmic algorithm for these reasons, and naturally linear-time algorithms outperform logarithmic ones for teeny inputs.
So to me what matters more are what some people might call "micro-optimizations", like data representations (memory layouts, access patterns with hot/cold field splitting, etc), multithreading, SIMD, and occasionally GPGPU. In a field where everyone is already competent enough to use decent to cutting-edge algorithms for everything with new papers being published all the time, your competitive edge in beating the algorithmic wizards doesn't come from improvements in algorithmic complexity so much as more direct computational efficiency.
My field is dominated by brilliant mathematicians but not always ones who know the computational cost of what they're doing or a lot of the lower-level tricks to speed up code. That's usually my edge over them in devising faster and tighter algorithms and data structures in spite of mine being a lot less sophisticated. I'm playing to what the hardware likes, towards bits and bytes and making each iteration of work much cheaper even if I'm doing a few more iterations of work than the really sophisticated algorithm -- the work in my case is drastically cheaper. The code I write also tends to be a lot simpler. If people think micro-optimized versions of straightforward algorithms and data structures are hard to understand and maintain, try understanding and maintaining a collection of exotic mesh-related algorithms and data structures never seen before in the industry with 20-page papers describing their steps mathematically.
As a basic example, I came up with a simple grid structure which ended up outperforming a KD-tree at our company for collision detection and redundant point removal. My stupid crude grid was so much less sophisticated algorithmically and I'm much dumber mathematically and algorithmically than the guy who implemented the KD-tree with his novel way of finding the median point, but I just tuned my grid's memory usage and access patterns and that was enough to outperform something much more sophisticated.
Another edge I have that allows me to survive in a field dominated by people much smarter than me is just really understanding how the user works, since I use the software I develop the same way. That gives me ideas for algorithms that really align very immediately with user interests. As a basic example there, most people try to accelerate things like collision detection using spatial indexing. I made a simple career-shaping observation almost a couple of decades ago for organic models that, for example, if a character places his hands on his face, a spatial indexing structure would want to have to split nodes and do expensive updates if the character then took his hand off of his face. If, instead, you partition based on connectivity data rather than vertex positions, you can end up with a stable hierarchical structure that updates very rapidly and never needs to split or rebalance the tree (only has to update bounding boxes every frame of animation)... things like this -- algorithms a kid with no heavy mathematical background could come up with if they just understood the basic concept, but ones that eluded the mathematicians since they weren't thinking of things in a way so close to how the users worked and were thinking too much just about properties of geometry and not how geometry was commonly used. I get along well enough by leaning more on general computational knowledge and user-end knowledge than algorithmic wizardry. So anyway, I haven't really found it that important to focus on algorithmic complexity.
Yes, complexity matters in the industry. If you end up designing something where a critical pathway scales as N-squared (doubling the number of something makes the system four times as loaded), you will hit your scaling bottleneck much faster than if you have something that scales at N.
However, it's usually not done as a proper, formal, proof that something is at a given complexity, so having a good intuition for what complexity a pattern of operations have is a good start.
I never think of big O in a mathematical perspective, I never think about big O at all, unless asked. I just see an algorithm in my head, and I can tell if it's bad because it does multiple loops through memory for each N, or if it does divide and conquer or something like that. If needed, I can translate that to big O notation in few seconds, but it's easier for me to just know how the algorithm/container works with memory, than to think about mathematical perspective.
The questions that are asked in interviews are there to find out if you can explain things and think in a logical way. The interviewer is also trying to find out if you can employ what you know to solve a related problem.
Everyone that has done any worthwhile studying of software engineering will have come across “Big O”, also to answer a good question about “Big O” you must also have some understand of standard data structures and algorithms.
When interviewing for a member of staff you are looking for someone that can learn the job quickly not someone that already knows a given set of detailed skills, so it can be very hard to choose questions that both the interviewer and the interviewee have a common understanding of.
So questions about “big O” can be very relevant to the interviewing process.
At least every year over my long time as a computer programmer I have had to fix code that was slow due to someone not understanding the correct data structures and algorithms to use, but you can solve these problems without having a detailed understanding of Big O. However people that do understand Big O tent not avoid these problems in the first place.