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?

  • 5
    @MM01 I've studied it in high school and University. Although I recognize it as a building block of a Programmer knowledge, I never used it in any of my job. – systempuntoout Nov 23 '10 at 12:03
  • 26
    What exact industry are you contemplating when asking this? Are you writing control code for a lunar rover, or a blogging platform? – Tim Post Nov 23 '10 at 12:16
  • 14
    @systempuntoout, you never, ever chose an algorithm which was faster than another because it was faster? – user1249 Nov 23 '10 at 12:21
  • 3
    @MM01 - If you are struggling with it, one of the easiest (albeit over simplified) explanations can be found here: rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation – Tim Post Nov 23 '10 at 12:26
  • 5
    @Systempuntoout, understanding and using O-notation does not imply rigid mathematical proof, but can convey in a simple expression how your algorithm behaves. If you need sorting in 1D you want a O(n log n) algorithm. If you want a Fibbonacci-number implementation you pick the one that runs in O(n). Even if you do not explicitly say it out loud, this is still the condensed version of the numbers of loops and recursions which is extremely usable. Saves a lot of words. (And for the nitpicky - yes, k is important too if it is significantly big or small). – user1249 Nov 23 '10 at 13:46

17 Answers 17

up vote 76 down vote accepted

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.)

  • +1 because the principles are important. In my experience of industry, its a consideration to take into account, not something to dwell on a great deal. That said - it you get asked about a comparison of (example) list insertion vs array insertion, or bubble sort vs quicksort then the interviewer is aiming to guage your knowledge. And get an appreciation of if you even think about complexity/run-time/scalability/performance. If you don't / can't think about these things there will be some jobs you won't know how to do well. Rare, but it does come up from time to time. – quickly_now Nov 23 '10 at 12:08
  • 5
    Well, it is possible, so is shooting at targets in pitch black darkness. Given enough bullets, you'll eventually hit the bull's eye. Then, experiencing the result of various designs and implementations factors in, which results in fewer bullets needed next time. Bad analogy, probably, but it accurately describes the way some software is written. I up-voted your answer. – Tim Post Nov 23 '10 at 12:14
  • But also note that "reeeally" performace is more often affected by issues that have nothing to do with complexity, but with black boxes out of your control. A mental model of those boxes is a must for optimizing anything. These considerations probably get invalid as N approaches infinite, which never reeeeally does. – Dr. belisarius Nov 23 '10 at 16:47
  • @Tim Post - I said " ... consistently implement scalable systems ...". Sure you can get lucky, but you cannot get lucky consistently. But I'm also prepared to accept that a really smart / experienced person could develop an intuitive understanding of complexity without going anywhere near a text book or computer science course. – Stephen C Nov 24 '10 at 0:34
  • Side note, it led to some good laughs at work when a male coworker told a female coworker, "Sounds like you've got a Big O problem", without realizing the other meaning of the term. She took it in the spirit it was meant, but couldn't stop giggling. – Paul Sep 21 '16 at 15:48

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)

enter image description here

  • 8
    +1: The worst way to find out your process doesn't scale is to have a bunch of screaming customers show up all at once. – Larry Coleman Nov 23 '10 at 13:13
  • 21
    @Larry, at least the screams scale linearly with the number of customers! – user1249 Nov 23 '10 at 13:17
  • 10
    Well, I guess that just shows how important big-O is: the sound is actually O(log Customers) dB. – MSalters Nov 23 '10 at 13:51
  • 4
    @MSalters, ok, I stand corrected: "the NUMBER of screams scale linearly with the number of customers". The sound level is a different matter. – user1249 Nov 23 '10 at 14:04
  • 1
    @Thorbjørn Ravn Andersen: I've read some studies that imply that it's more of a logarithmic scale, which is why certain classes of customer complaints are so important! They indicate that, the larger the customer base, many more people have that problem, and just aren't saying anything or are going to the competition. – Steven Evers Nov 23 '10 at 15:00

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.

  • Making a mobile app is not just a case of throwing together a GUI, but I'll forgive you for making that statement in 2010 :) There is complexity in architecture, threading, data storage, networking queues, in mobile. But raw Big O is irrelevant (at least in iOS) because you should be using native data structures and algorithms. – PostCodeism Nov 20 '17 at 19:17

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.

  • Where you really notice this is when looking at code written by someone who hasn't internalized Big-O, and is surprised that their subsystem performs so horribly in production. Even a basic understanding is enough to make you question four nested foreach loops over the same two huge arrays... – eswald Nov 23 '10 at 19:27

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.

  • 1
    I actually think this casual "n+1" queries thing is sort of dangerous. In particular, I've seen code that made n^d queries (where d >= 2) dismissed as "n+1", which made a truly horrible situation look merely bad. – philosodad Jul 28 '12 at 12:01

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.

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.

  • Any good collections API makes these guarantees, for example the Java collections API also has these guarantees in its documentation. – Ken Bloom Nov 24 '10 at 2:09

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.

protected by gnat Sep 20 '16 at 14:32

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.