Should we care if a prospective hire understand Big O notation?

Question

A colleague of mine caused a long e-mail conversation by saying:

Of the probably 30+ people I’ve given a phone interview to, not a one (including people with Masters degrees in CS!!) has been able to tell me the big O of bubble sort- or any other sort for that matter, and maybe 2-3 seemed to have an clue what I was talking about.

Am I expecting too much of people with CS degrees? Maybe. But people with undergrad and Masters degrees in CS?

The last few people with CS degree’s couldn’t even describe how bubble sort worked.

The potential developer would be working on web based line of business apps, not scientific or game programming. Some people in the conversation feel that computational theory isn't so important when using modern framworks, i.e. no one should be writing a sort after CS 101.

Personally, I think that the kind of person who would care about the underlying theory is going to be a better programmer.

What do you think?

Answer 1

Regardless of whether it will be important during the position for them to understand this (which is debatable, even if you're 'just' doing web B2B stuff), I expect people with computer science degrees to understand this particular thing. Imho, this is something that's taught in a lot of intro CS classes.

Answer 2

It's a reasonable question to ask someone who claims to have a CS degree. It's a fairly basic and fundamental concept that they should have learned. If they don't know that it could be a sign of other problems.

However, I might not expect someone who learned to program on their own and doesn't have a CS degree to know that.

Answer 3

Just In Time Learning. They should only know it if they need to know it. However, they should always be aware that it is there for them to learn.

I personally know how to deduce the growth of an algorithm, but I don't think it really helped me in writing code. Figuring out how fast or slow an algorithm is, is more intuitive than scientific, until you have to know; then it becomes scientific and you'd better have someone who knows how to do it.

Answer 4

It's more important to know the concept of time complexity than the specific Big-O notation. Even if someone can't tell you that a doubly nested for loop is O(n^2), they should know that using it all the time is probably going to cause slowdowns.

Answer 5

I don't require memorizing algorithms, but if the guy doesn't know what is O(n^2), I reject him, and I think You should do the same.

Answer 6

I think you've been getting some serious duds applying for your positions. To be honest, I'd really wonder if they actually have the degrees that they claim to have. Big O notation is NOT an optional consideration in computer science; understanding it and understanding why it is important is a critical requirement for really understanding computer science.

It doesn't really matter what you're writing for; Big O notation is important to understand. Even if you're using modern frameworks, you need to know this stuff. For heaven's sake, just because modern frameworks provide you with a hashtable implementation doesn't mean that you shouldn't know what the underlying Order of using a hashtable is. In fact, the fact that they provide the tools makes it MORE important to know what the underlying theories are, because you don't have the ability to investigate the source code; you HAVE to know how a hashtable works to be able to use one, not just write one.

Seriously, if you have a person with a CS degree who can't describe how a bubble sort works, show them the door. IMMEDIATELY. No apologies, no questions... the simple fact is, they're either lying about their degree, or their knowledge is so poor that they won't be useful (most likely a combination of both).

Edit: Let me clarify. I'm not trying to indicate that any prospective candidate needs to know exactly what a bubble sort is and how it works (I'm willing to understand that some knowledge has "aged out"). But they had better (in my opinion) know what the algorithmic implications of such a sort are versus another type of sort; if they don't, they don't have the knowledge to work successfully in a software development job, in my opinion.

Answer 7

I'd be concerned, but not because a web developer necessarily needs to know complexity theory to do their job.

My main concern would be that getting through a BS in CS without picking up at least the basics of Big O demonstrates that you weren't paying attention at all!

Answer 8

Yes you should care, but you are asking the wrong questions.

Who really cares or knows about bubble/insertion/selection sort when there are libraries and better implementations like quicksort, mergesort, heapsort, radixsort?

They should know the complexity of at least 1 sort.

What they should really know is the complexity of containers which is used much more often than sorting algorithms. Knowing the difference between a linked list, array, and hash table should be required.

Answer 9

The big issue is that behind the scenes in these tools and frameworks they're using, routines are running that have O(whatever) impacts. When you're writing a little app to work on a small dataset, it may not matter. When you work with a database with thousands, even millions of records, the design of the schema and data stored, and how you access it from these high-level tools will have at least the potential to invoke an O(n*n) algorithm, and understanding what that is, and why they are slow, will make it less likely to get into that problem. Also, if you do, they'll understand there's likely an algorithmic issue they need to revise things to avoid, instead of dithering around the edges trying to "optimize" by reducing 'k' while ignoring 'n' and not looking for a lower O() solution.

Answer 10

A computer program is a sum of its parts. To create a program that is the best it can be, each part must be created the best way it can be.

Not knowing the nomenclature for perhaps the most fundamental and important aspect of superb programming is certainly a red flag. I don't know what types of education these people received, but perhaps they simply know the concept by another name (but I doubt it).

If it were up to me, I wouldn't hire a software engineer who can't tell me how efficient an algorithm is.

Answer 11

might be worth asking, but I wouldn't make any decisions based on it. very rare that it matters unless you are hiring an algorithm coder.

Answer 12

He might not know big-O; in this case, he should know enough hot topics to cover this.

I mean, you have to know something! If someone's something approaches empty set, why would you want him in?

Answer 13

Rejecting people for something that they could learn on wikipedia in 5 minutes is rather pointless. But if it's important for you feel free. You may just be toss the best developer for you group over a simple topic they will never use, forgot the term of, of simplely never heard of becasue they have either never taken programming classes of been in a class that it was covered.

Answer 14

I think it's more likely they don't remember bubble sort. Most learn that in the first year of school and it isn't important after that. It is more meaningful if they can't figure out the big O of an algoritm they know well.

Answer 15

This is highly subjective and varies a lot.

For example, I work with 4 people, 3 with a Master Degree and the other with no degree at all. For those "simple" tasks, like CRUD applications, the guy with no formal education is the most productive.

The others prefer more difficult tasks and do not work with motivation if I handle them a CRUD application.

So, what I am saying is that there is no need to know certain subjects if your work is just "simple" tasks.

Answer 16

I wished that my study had involved the underlying technology. I had to do a minor to get some basic understanding of data structures and algorithms which I find a bit sad. In defence of my study they did explain the big O notation. The idea behind it should at least be known. I do agree that for writing "boring software" you do not need to know what a hashtable is. Higher lever languages and frameworks provide you with just about everything out of the box.

The general consensus seems to be, "You're not going to write a better implementation, so don't even bother with it."

Answer 17

You fail to make a distinction between understanding Big Oh notation (or time complexity in general) and having memorized the time complexity of a bubble sort. I can give you a very thorough explanation of the former, and could not remember the latter to save my life. Of course, if you sat me down in front of (pseudo)code for a bubble sort I could tell you the time complexity of it.

Answer 18

Big-O is hardly relevant to doing web development, so just forget about that. Instead, focus on your goal - you said:

Personally, I think that the kind of person who would care about the underlying theory is going to be a better programmer.

I think you're on the right track here, except that caring about Big-O indicates the candidate will be a good systems programmer while understanding, say, details about the HTTP stack or the internals of Ruby on Rails would indicate they'll be a good web developer.

Think of it this way, if I want to hire a mechanic to work on trucks and during the interview I start asking about the performance considerations of compact cars... would it be shocking if the guy didn't care? Probably he cares a whole lot about the equivalent topic in his area of expertise (and the kind of work you're potentially going to hire him for).

Answer 19

Well i don't have a degree in CS and i'm self taught on what little i do know but even i have started to try to learn bubble sort amoungst others, just for the sheer fact that if it is widespread like it is there must be a reason to know it.

Answer 20

First, ~10% of interviewees in a phone screening having any clue at all seems about right to me. In my experience, it's always the case that 80-90% of applicants for development jobs really shouldn't even be in the business. That's why you screen.

On the other hand, be wary of focusing on things like bubble sort. Yes, back when I learned CS it's the first sort we learned, and was the base comparison for other algorithms, but if you think about it there's no good reason for this, and it's absolutely possible for a very good algorithm course to gloss over bubble sort and start with selection sort or something. And I'd be very wary of asking directly "what's the big O of ...", that's the kind of question where someone could easily just draw a blank during an interview.

On the other hand, developers should be able talk intelligently about Big O notation and algorithm speed generally. But I think you'd be better off asking general questions about it, rather than asking about specific (largely archaic) algorithms.

Answer 21

@Malfist: I agree. Give it a few years after you graduate and you will forget most of factual stuff, if you don't use it in practice. What will be left, is the basic remembrance what it was and from what opera, so that you know where to listen to it again whenever you need it. I learned and tried many kinds of algorithms as a student, but I do not even remember their names today.

Like we were taught in university: A professional is not the one who knows everything, but he who knows where to find the information he needs.

Answer 22

I don't have a CS degree, but I've tried to keep up, and Big-O is a concept that I've come across constantly. If you don't know what this is and you don't have a CS degree then you either don't try to improve or all of your learning is of the form "learn widget Y with framework X" and you're not going to be very good at conceptualizing. If you don't know big-O and have a CS degree, ... well, I can't really figure out what you were doing, but it wouldn't fill me with confidence. It's chapter 1 in CLRS, it's a pretty intuitive concept.

I've been on lots of interviews, in my experience interviews that don't ask tough questions (and this is nowhere near a tough questions) mean a place where most of the coders are ... er... not so good. You don't want to be that place, and I can't imagine that you want people who aren't aware of the consequences of their decisions ("I'll just iterate through this array every time I want to find somehing...").

As a point of reference, in my (sadly unsuccessful) google interview, this kind of question would (rightly) barely rate for the phone screen.

Answer 23

Here's my take on it.

Background Knowledge vs. Detail Knowledge

Knowing the Big-O of bubble sort, or any other sort, is a piece of "detail knowledge". Knowing what Big-O is would be "background knowledge".

Someone who is good at their chosen field will have a good supply of "background knowledge" to draw upon. Background knowledge allows for a fundamental understanding of a problem, and how best to approach it.

Detail knowledge is much less important for the problem solving process, and more important for the implementation of the solution. Obviously, the more detail knowledge you have, the faster you can work, but knowing details without background can cause someone to take an entirely incorrect approach. Knowing background without details is much preferable, as details are usually trivial to learn and implement.

How the Programmer fits the Job

I am ten years out of university. You can bet your bottom dollar that I have forgotten the big O of almost every algorithm I learned in CS 100. When was the last time I implemented a custom sort algorithm in ten years of web programming? Never. And unless you're implementing a bunch of custom sort algorithms specifically, you shouldn't put much weight on whether someone knows the "detail knowledge" behind it, as it's something they or you will probably never need to write.

On the other hand, could I tell you what Big O was? Most definitely. Could I research and come up with sorting alorgithms with a task-suitable Big O very quickly? Most definitely. Could I compare two web application process stacks and decide which one had the better Big O? Yes. Background knowledge beats out detail knowledge hands down here.

As long as a programmer (or anyone in any field) understands the fundamentals on a solid level (background knowledge), they will have the potential to be a good programmer. If they have acquired a lot of detail knowledge as well, through study or experience, then they can probably program faster, and maybe more accurately, as well. You can be a good programmer with no detail knowledge and lots of background knowledge, but the likelihood of being a good programmer with lots of detail knowledge and no background knowledge is much, much lower.

Tailor your Interview

Your interview should weigh all this accordingly to decide which candidate would be the best fit. For your particular case, I would make sure to hire someone who understood what Big-O was, as obviously they have more solid background knowledge to draw on. But dismissing them because they don't know the Big-O of bubble sort is silly, unless the job specifically deals with bubble sort in a serious capacity.

I could come up with a hundred similar detail-oriented questions to confound an interview candidate, and I guarantee that you or anyone wouldn't be able to answer all, or even most of them. When was the last time you wrote a database indexing algorithm from scratch, or even a B-tree, or took something to Backus-Naur normalized form (CS 230 in my day)? How about your own TCP/IP layer protocol (SEng 450 in my day)?

I can tell you what these things are and how to do them, but you tend to forget details after they become unimportant. However, I could find them and do them quickly if I had too. Make sure your interview weighs what background knowledge is important for the position as well as what detail knowledge is important.

Answer 24

WHere are these guys getting their masters degrees?

Is this like the spam emails I get all the time, send us some cash and we'll send you a degree?

I would think that anyone taking a basic, undergraduate class in numerical methods would have learned this.

Answer 25

One more semester to go and I will be graduating with a degree in Software Engineering: Computer Programming, and Big O was required in the Data Structures classes. Those classes were only required for programmers though, not for web programming or web development, as such I am not surprised that people coming out of school with a "CS" degree for web development have not learned about Big O notation.

Answer 26

I would be concerned if they didn't recognize big-O notation as a way of speaking about algorithm complexity.

I would not be worried if they couldn't remember big-O of a bubble sort off the top of their head. I would be worried if they couldn't derive it.

Here's the reason even web programmers need to big-O: they need to recognize when something is no longer linear. They also need to understand that processes can be non-linear. Basically, they need to be able to see how long something is taking on different kinds of input, or how long something is taking over time, and have the intuition "oh, I bet this process is O(n²)" or "O(n⁴)" or "O(2ⁿ)", and not the much less helpful thought "gee, this is slow."

As an example of where web programmers get tied up in algorithmic complexity, allow me to point to regular expressions. It is very, very easy to create a regex that isn't O(n) in its input size. When that happens and you hit general performance problems on large input, you need to have the conceptual tools to recognize what's going on.

Answer 27

I don't see how someone memorizing bubble sort, insertion sort, or any other sort and their corresponding time complexity implies that they know much, or even anything, about computer science nor would make them an even-close-to-competent programmer.

Personally, I think that the kind of person who would care about the underlying theory is going to be a better programmer.

This is important. So how do you test to find out if someone cares? Why not give them a problem, two fairly simple algorithms that accomplish the same thing in different time complexities, and then ask them to describe the differences and why one might be better than the other. And, if you can, make it a problem applicable to your domain area. If they can tell you why one of the two algorithms is better, and demonstrate the ability to figure it out, then they are likely stronger in this regard.

For your domain, I would want to know if they could recognize time complexity related problems more than I would care about Big-O notation. Would they simplify a for loop that made calls to a database to a single SQL query if the opportunity presented itself?

Answer 28

When you want someone to design your home, the person with the best credentials typically is the person with foundational (and hopefully experiential) architectural knowledge.

When you need surgery, the person with the best credentials typically is the person with foundational (and very hopefully experiential) medical knowledge.

Granted, people can learn things from books and people can learn things from sites like Wikipedia. But when one gets down to the brass tacks, so to speak, the engineer or technician who has the deepest knowledge of their field is likely the most capable and quite possibly the one to bring the best results.

Software Engineering is a profession, and like all technical professions benefits from foundational knowledge of the field. If interviewees didn't remember the term Big-O, I would be irked (have they ever heard of it? why not?). If they couldn't analyze an algorithm and at least give a very reasonable assessment of the worst run-time (average preferable), the interview would be done early. I would no more trust the applicant to build complex code than I would trust an average teenager to design and wire my home electrical system.

To reiterate: having a sense of algorithmic complexity is foundational. One may be able to learn how to assess complexity by reading up on it "when one needs it", but the hard fact is that if one is writing code, one needs to be aware of the ramifications of one's choices - the good software engineer should have this knowledge (and this tool) from square 1.

Answer 29

JUst because somebody dosn't know/remember big-O or how a bubble sort works, dosn't mean they will not be a good developer. Most people don't know how a keyboard works, but is that as important as knowing how to use one? Seems like a petty reason to pass somebody up for consideration.

Answer 30

If you phrased it as "big O", i can easily see not knowing what it is.

When i studied, it was called order, and written as O( n^2) but it was never ever referred to as "big Oh".

Answer 31

I dedicate this post for all of You who say it doesn't really matter for web frontend coders.

In the interview for a python coder:

• how would You get the last element from the list?
• that's easy! my_list.reverse() ; print my_list[0]

Answer 32

You should care because it's not that hard. And if they've (allegedly) done a computer science major and don't know it, there's something wrong (with them).

Answer 33

Yes, but just the basics:

• O(n) to search for an item in an unsorted array
• O(log n) to search for an item in a sorted collection (binary-search tree, SortedDictionary, etc)
• Expected O(1) to access items in a hashtable
• O(n log n) to sort collections

Answer 34

They should know what Big O means, but IMO, a good understanding of design patterns is more valuable.

Answer 35

Should they know what BigO is and how to determine it? Absolutely. Should BigO have to be remembered for bubblesort? I don't think so. It's not all that common that anyone will be writing their own sorts...most of the collections have pretty solid sorts and even if they have to they could google the bigO of most known sort schemes.

It's more important that they understand the concepts of algorithm analysis for their own algorithms...not remembering arbitrary facts about bubblesort. Seeing average case and worst case for your own computationally intensive code is more important.

Answer 36

I've been programming successful commercial apps for 20 years, have interviewed many candidates for companies I've worked for, and I've never asked about Big-O. I'm embarrassed to say that I actually had to use Wikipedia to remind myself how Big-O notation worked, although I did remember the general concept from my first year CS course. I asked myself how I could have forgotten something so fundamental, and then realized that, aside from lower-level systems-type programming, there are only really two orders I care about when reviewing my average LOB programmer's code: O(too slow) and O(fast enough).