Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
4  
@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
20  
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
10  
@systempuntoout, you never, ever chose an algorithm which was faster than another because it was faster? –  user1249 Nov 23 '10 at 12:21
2  
@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
4  
@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
show 6 more comments

16 Answers

up vote 56 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.)

share|improve this answer
4  
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
show 3 more comments

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

share|improve this answer
4  
+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
13  
@Larry, at least the screams scale linearly with the number of customers! –  user1249 Nov 23 '10 at 13:17
4  
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
1  
@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. –  Steve Evers Nov 23 '10 at 15:00
show 1 more comment

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.

share|improve this answer
10  
+1 for "Big O will come and eat you" ..fantastic! –  systempuntoout Nov 23 '10 at 13:40
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
show 1 more comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
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
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
show 1 more comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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