Is big-O really that relevant when working in industry?

Question

In every interview I have been in, I have been quizzed on mathematical analysis of complexity, including big-O notation. My question is, how relevant is this test to development in industry? How often do you reeeally use it, and how necessary is it to have a honed mindset for the problem?

Answer 1

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

Answer 2

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)

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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.

Answer 7

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.

Answer 8

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.

Answer 9

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.

Answer 10

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.

Answer 11

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.

Answer 12

It's probably used in places where they are developing API's for consumption. The C++ STL is one of the few API's that has complexity restrictions imposed on it's algorithms. But for the everyday working programmer/senior programmer/designer/architect it doesn't cross their minds much.

Answer 13

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.

Answer 14

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.

Answer 15

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.

Answer 16

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.