Ned Batchelder : Blog | Code | Text | Site Big-O: how code slows as data grows » Home : Text |

Created 18 October 2017 There's this thing in computer science that working programmers talk about, called "big-O". When a software developer feels bad because they don't have a Computer Science degree, and they feel a bit inferior because of it, it seems like big-O notation gets mentioned as the indicator of the grown-ups table. Big-O isn't as mystical as it appears. It's wrapped in mathematical trappings, but doesn't have to be more than a common-sense assessment of how your code will behave. My goal here is to explain big-O in ten minutes so that you can reason about your code, without getting into esoteric concerns. I'm using Python examples in this write-up, but the concepts apply to all programming languages. ## The basic ideaBig-O notation is a way to understand how code behaves as its data gets larger. To put it in rhyme form:
Imagine you have a chunk of code that does something to a bunch of data. You'd like to know how much slower the code will go if you give it ten times more data. That's what big-O describes. You might imagine that the answer is of course, ten times slower. But that's not the way real code works. One algorithm might go a hundred times slower. Another might not go any slower at all. Big-O is a way to analyze the code and determine the slow-down factor. The rhyme is cute, but it captures the essence. Big-O isn't about how fast a particular piece of code will actually run with a particular data set. Big-O is about the relationship between the size of the data, and the time the code will take. As your data changes size, how will your run time change? How code slows as data grows. Before jumping into the nitty-gritty, let's look at a real-world example. Suppose I give you two jars of beans, a small one with 100 beans in it, and a large one with 500 beans in it. Each has a label saying how many beans are in the jar. I ask you to tell me how many are in each jar. The time it takes you to determine the count is the same for both jars: you just read the number off the label. The time didn't depend on how many beans there were, assuming we can trust the label. Now suppose I give you the same two jars, but without the labels. To determine how many beans there are, it will take 5 times longer for the large jar, because now you have to count each bean. With labelled jars, determining the count was a constant-time operation: it took the same amount of time no matter how many beans there were. In the unlabelled scenario, we have what's called a linear-time operation: determining the count takes more time if there are more beans. The time is proportional to the number of beans. Big-O is about doing the same kind of reasoning, but for data structures and code instead of jars of beans. ## TerminologyThe letter O is used because it describes the run time as being "on the Order of" something, which is a mathematician's way of saying that two things grow similarly. O(N) means that the run time is on the order of N, or that it grows in the same way that N grows. Another term people use for this is "algorithmic complexity," which sounds super-advanced, so feel free to throw that around and impress your friends. The notation looks like a function: O(N) has similar syntax to sin(x). But it isn't a function, it's just a shorthand. "O(N)" is "order of N", and "sin(x)" is "sine of x", so those too-clever mathematicians used the same syntax. Don't let it throw you. ## What the notation meansLet's start by understanding what the notation means, and then we'll get into how to determine it. When talking about the big-O run time of a piece of code, the size of the input data is given a letter name, usually N or n. Then the big-O is an expression in N that says roughly how many steps the code will take to execute. If someone says an algorithm is O(N), that means that the number of steps is proportional to N. If you give it ten times more data, it will take ten times as long to run. Counting unlabelled bean jars is O(N). O(N Some other common expressions you might see are O(log N) and O(N log N). ## Analyzing codeTo determine the big-O run time of your code, first decide what aspect of your data is the one that grows. What is the interesting size in your input data? Usually this is pretty obvious, but it's good to be explicit about it. As an example, let's say I have a list of key/value pairs, and I want to find the value for a particular key:
In this case, the variable size of the data is the length of the list of pairs. We'll call the length of the list N. Using your understanding of the code, look at each part of it, and total up how many steps will be executed if the input is size N. At this point, you might be asking, "what counts as a step?" That's a great question. This may seem surprising, but in lots of ways, it doesn't matter. The important thing is to understand where your code will do more work when N is larger. And as we'll see, there's a lot about the number of steps that we are going to ignore anyway. When our function runs, it's going to look through the key/value pairs until it finds a match. The match could be anywhere in the list, sometimes near the front, sometimes way in the back. On average, we'll find it halfway through the list. This is one of the ways big-O is not precise: it's a characterization of the average run time of a piece of code. Sometimes we'll run this function, and we'll get lucky and it will find the value in the very first element. But on average, we'll have to look through half the elements to find it. Let's look at the code line by line:
Since on average we'll find the value after examining half the elements, we'll execute this loop N/2 times. In this statement, we have N/2 steps to get the elements out of haystack. We have N/2 steps to assign each of the keys to key, and N/2 steps to assign the values to val. This statement contributes a total of 3N/2 steps.
We'll do this comparison N/2 times, so now we have a total of 3N/2+N/2 = 4N/2 = 2N steps.
This line will only be executed once, so now our total is 2N+1. Notice we counted the assignments as 1, and the return as 1. What if returns take longer than assignments? It doesn't matter. The key thing is that the run time for assigning one name is independent of the length of our input list, and the run time for returning the found value is also independent of the length of our input list. They are each constant as far as N is concerned, so we count them each as 1. Finally, the last line (returning None if we didn't find the value) is also a constant 1, so our grand total is 2N+2 steps. When describing the big-O run time, we only care about the most significant component. This is because we are looking at how the run time changes as the data gets bigger and bigger. As N gets larger, the +2 part becomes less and less significant, to the point that it is irrelevant. So we drop everything but the biggest-exponent piece. 2N+2 becomes just 2N. And the constant multiplier is irrelevant because O(2N) will double if N doubles, just like O(N) will. So we drop the coefficients also. After dropping the irrelevant stuff, 2N+2 becomes N, so our find_it function has a run time, or algorithmic complexity, of O(N). ## Building upNow suppose we need to look through all the values, and if they are also keys, then sum all of those keys' values? (A little confusing, and contrived, I know.) This code will do it for us:
Let's figure out the algorithmic complexity of this code. Again, N will be the length of haystack, the number of key/value pairs in the list. This time, our loop will always be over the entire list, so this line will run N times:
There are three steps each time we run this line, so that gives us 3N steps. The next line is where it gets interesting:
As we analyzed earlier, the find_it function is O(N). This loop will
execute it N times, so this line requires N With code like this, If you have ten times the data, it will take a hundred times longer. With a thousand times as much data, it takes a million times longer. Be careful of quadratic algorithms. If you get any interestingly sized data, your program can become very slow. This is the point of analyzing the algorithmic complexity of your code. Often, programs start with small data sets, and then grow as they are used more. That data growth implies some run time growth. Thinking about that as you write the code can help you avoid problems further down the road. ## The ideal: O(1)It seems magical somehow, but there are algorithms that are O(1): they deal with varying amounts of data in a constant time. Give them a thousand times as much data, the run time doesn't change. Getting the length of a Python list is O(1), because like our labelled bean jars, they record the count in an easy-to-read way. Hash tables are the classic example of a great O(1) algorithm. Looking up a value in a hash table is a constant-time operation. Python's dicts, Ruby's hashes, Perl's hashes, Java's HashMaps, etc, are all hash tables. Finding a key in a million-element dict is just as fast as finding one in ten-element dict. That seems magical, but it's true. If you're curious about how it works, Stack Overflow has some good answers to How does a hash table work? ## The graphNo discussion of big-O would be complete without an illustration of how different run times grow with the size of the data: The horizontal axis here is the size of the data, and the vertical axis is the run time of the code. Neither has any units, because this is still just a crude characterization with lots of details omitted, as big-O always is. Notice how quickly the red O(n Another note about terminology: sometimes complexity is referred to with
short-hands based on the exponent of the speed. O(N) is called "linear", O(1)
is called "constant", and O(N ## PrimitivesWhen analyzing code, we need to know how many steps to count for each of the individual operations. Every programming language provides types, data structures and libraries. Each operation on those structures will have its own complexity that contributes steps to your overall program. You'll need to know what those are in order to accurately understand your own code. Here are some for Python data structures:
In all of these, N is the size of the list, dict, or set. Looking up values in a dict or set is O(1). This is why people love them so much. Often a good first guess about how to make a Python program faster is: find the place where you are searching a list for a value. Make that list a set instead. More details about Python behavior is at the Time Complexity Python wiki page. ## Be reasonableUnderstanding the algorithmic complexity of your code is a powerful tool. Choosing the right algorithm is the best way to make code go faster. But like any tool, big-O can be over-applied. It's important, but it isn't the only consideration. For example, searching a list is O(N), but if the list is small, or if you only need to do it once, then who cares? Just write the simple code, and move on. Another factor to consider is that big-O discards the coefficients. You
might have two algorithms to choose between. One is O(N) and another is
O(N ## Some final detailsAn important thing to remember about algorithmic complexity: it's a rough characterization of the average behavior of a chunk of code over typical data. As an example, above I said that appending to a Python list is O(1). In truth, when you append to a list, it's either very fast, or it's slow. How slow it is depends on how long the list is. That sounds like O(N), but appending is clever: the slow option gets slower as the list grows, but it also gets less and less frequent. This net result is that on average, the operation is O(1). If you read more about big-O, you may see the word "amortized" thrown around. That's a fancy word for "average," meaning that individual occurrences don't all behave exactly the same, but over the long run, averaging over many operations, the behavior has a certain characteristic. The analysis we've been doing is for the average behavior. Lots of
operations can behave much worse in unusual circumstances. Adding a key in a
dict and looking up a key are O(1), which is true for typical data. But if you
understand the internals of dicts, you can carefully craft a set of keys that
will perform terribly, with O(N) behavior. Filling that dict would take
O(N The simple analyses we've done here have only considered a single variable, the "size of the data." But real-world data may grow in a few dimensions at once. If our find_it function from above is comparing strings, then we have to consider that the time to check if two strings are equal is linear with the length of the strings. The real run time might be O(N*k), where N is the number of strings, and k is the length of the strings. In real use, the length of the strings might stay small and bounded, so we can ignore that factor and just call it O(N), but you might have a case (bioinformatics?) where the strings grow very large, and you have to take it into account. ## Run with itI hope this has given you the tools to analyze code and make good algorithm
choices. There's much more to algorithm analysis if you want to get into the
true computer science aspects of it, but this is enough for working developers.
With practice, it will become second nature to think about the algorithmic
complexity of the code you write, and you will recognize the dreaded
N Full disclosure: There are a bunch of simplifications in this piece that are common among working programmers, but computer scientists might be unhappy with them. If you are interested in a deeper study of these topics, A Gentle Introduction to Algorithm Complexity Analysis goes into lots more details. | ||||||||||||||||||||||||||||

## Comments

Rahul3:43 AM on 20 Oct 2017Probably the best intro to Big-O. Good Job and thanks for posting this Sir.

Veky3:07 PM on 20 Oct 2017In fact, counting labelled bean jars is O(log N), because you need time to read the label. But it just shows that when the complexity is O(log N), you can probably treat it as constant anyway. Logarithm of _anything_ is at most a few hundred anyway. :-D

Moschops1:08 PM on 26 Oct 2017Then the mathematicians start talking about it and we realise we weren't at the grown-ups table after all :)

pyon1:13 PM on 26 Oct 2017You should be ashamed of this post. How dare you mislead your readers? In amortized analysis, earlier cheap operations pay the cost of later expensive ones. By the time you need to perform an expensive operation, you will have performed enough cheap ones, so that the cost of the entire sequence of operations is bounded above by the sum of their amortized costs. To fix your list example: a sequence of cheap list inserts pays the cost of the expensive one that comes next.

Ned Batchelder4:41 PM on 26 Oct 2017@pyon: It sounds to me like your point is the same as my sentence, "the slow option gets slower as the list grows, but it also gets less and less frequent. This net result is that on average, the operation is O(1)." I'm not sure what you think is missing from that, or what level of shame I should feel. Right now I feel none. :)

pyon8:11 PM on 26 Oct 2017No, my point isn't the same. Note that, according to the definition of amortized analysis that algorithms books give:

(0) The cheap operations are required to run before the expensive ones whose cost they amortize. This part is crucial, and it doesn't logically follow from your use of “average”.

(1) It is perfectly possible for one kind of operation to pay the amortized cost of a completely different kind of operation. For example, in the amortized analysis of pairing heaps, amortized O(1) merges pay the cost of amortized O(log n) deletes. There is nothing to average here.

You should be ashamed.

Ned Batchelder8:40 PM on 26 Oct 2017@pyon: it sounds like you have some valuable knowledge to share. It would be great if you could just do that, rather than sneering and trying (literally) to shame me.

pyon8:45 PM on 26 Oct 2017Normally I should have nothing to say. People could just, you know, actually read algorithms books. But when someone is wrong on the Internet...

Ned Batchelder8:53 PM on 26 Oct 2017When I find someone wrong on the internet, I try to educate them. You have a different strategy: snipe at them anonymously.

You haven't explained yourself. If amortization happens over a large number of operations, as data grows large, why does it matter if the expensive operation happens first?

You seem to be focusing especially on the word "average". Maybe you are reading something into it that I didn't intend?

pyon9:02 PM on 26 Oct 2017Because that's how amortized analysis is *defined*: you first pay for it, only then can you use it. By “it”, I mean the “right“ to perform expensive computation. But you could just read an algorithms book. (Damn, you tricked me into trying to educate you. Well done.)

Ned Batchelder9:21 PM on 26 Oct 2017I understand more about your point, thanks. This piece left out many details; I would not put this operations-ordering detail on the list of possible things to add to it. I'll stand by it as written.

I think it is sometimes difficult for experts to understand what can be omitted in introductory material.

Rick Landau2:33 AM on 30 Oct 2017@pyon: This post came from an excellent presentation on improving your code by thinking hard about it. The digression into big-O was intended, I think, for programmers who were not accustomed to thinking about their code that way. As an introduction to the topic, it correctly hit the high spots and avoided second-order details that would detract from the message. A good didactic lesson for non-experts.

Susan Senator4:32 PM on 30 Oct 2017@pyon: How dare you go onto someone's well-intentioned, well-thought-out, experienced piece and try to shame him? This is not how one should express themselves, even from behind the safety of a screen. Please consider how you deliver a message, as much as what your point is. Full disclosure, to be civil: Ned is my husband and a more honorable, wise man you will never find.

pyon2:12 AM on 2 Nov 2017@Rick @Susan Maybe the world would be a better place if programmers, you know, actually knew computer science. tl;dr: Watch me care.

Ned Batchelder12:37 AM on 3 Nov 2017@pyon: thanks, your comments here have been instructive. https://nedbatchelder.com/blog/201711/toxic_experts.html

Justine Akehurst1:10 AM on 3 Nov 2017@pyon can be found here as well: https://cstheory.stackexchange.com/users/6634/pyon

Eddie3:59 AM on 3 Nov 2017Hi Ned! There is a sharp distinction to be drawn between knowledge and character. Don't let this thread get you down. You have far more than your fair share of both, while sometimes your interlocutors will visibly falter on one or both.

jokane1:50 PM on 3 Nov 2017I happen to have read some algorithms books, as pyon suggests. I notice on page 452 of Cormen, Leiserson, Rivest, and Stein that amortized run time, when using the aggregate method, is defined as

T(n)/n, in whichT(n)denotes the total run time andndenotes the number of operations. This is an average, just as the original post suggests.Yes, there are other methods for amortized analysis that are not based on averaging —I'm thinking of the accounting method and the potential method, which are described later in the same chapter of CLRS— and those methods are indeed based on overcharging earlier operations to pay for later ones. But there is no "shame" in introducing a subject the same way that the most widely-used algorithms textbook does.

Aron Griffis2:17 PM on 3 Nov 2017Ned, thanks for the writeup—I always appreciate the effort you make to make things easy to understand.

I find that the only algorithmic complexity that I normally avoid is O(N²). It's become automatic and subconscious to un-nest loops over arbitrary-sized data, usually by throwing the data into a hash first so I can use a single loop with hash lookups. Of course, the technique isn't always appropriate, and it's slower for small data, but it might be the most common tool for avoiding quadratic complexity.

Grant Goodyear5:48 PM on 3 Nov 2017Nice write-up.

Note that one of the things that makes scientific computing painful is the fact that even a simple matrix multiply is O(N**3). [For the pedantic, yes, it is possible to do slightly better, but the matrices have to get truly enormous before the cost of the additional complexity is outweighed by the slight reduction in order.] Routine Hartree-Fock (quantum chemistry calculations) are O(N**4).

Wayne McDermott7:05 PM on 3 Nov 2017Well that was 10 minutes very well spent! Thank you.

Christy Heaton12:25 AM on 4 Nov 2017This is a fantastic overview of Big O. Thank you for writing this up!

## Add a comment: