Page Title

# Schindlabua's guide to Big-O notation Hi! Big $O$ notation (also called Landau notation) is a way for programmers to estimate the efficiency of their code, by looking at how it will perform with larger and larger inputs. @plot1@ In this tutorial we will look at what big O is, how you can find it, and how different time and space complexities compare. By knowing and reasoning about code with big O, you will learn to write more efficient algorithms, and at a glance see how well a piece of code will perform given lots of data! A small thing before we start: I will stick to JavaScript, but the same concepts apply to any language. If anything is unclear or you'd like to see changes made, drop a comment! ## A first example: $\Theta(n)$ Here's a piece of code that finds the largest number in an array: ```javascript function find_maximum(list){ let max = 0; for(let element of list) { if(element > max) max = element; } return max; } ``` You have probably seen this one before. The question is: How fast is it? And how well does it scale? There are a few ways we could test that. We could create lists of different lengths (like 1, 100, 10000, 1000000) and do a million runs each; and then look at the average time taken to get some pretty good statistics. And those kinds of tests are very important! The only real way to understand code performance is to watch it perform. However, it's also very dependent on what machine your are running your tests on, and what programs you have open, how hot it is outside... Big-O, which we use to measure "time complexity", is a bit more fundamental than that, and you can even do it yourself with just a finger, no expensive tests required. Let's try: ### Finding $\Theta$ For this exercise I want you count how many *lines of code* the function call `find_maximum([1,14,28]);` goes through. Obviously there is a for loop, so some lines will be repeated a few times. Go ahead, I'll wait. ![](https://i.imgur.com/dcHmoCU.png) Alright. Depending on how exactly you counted, you should have arrived at something like $14$: $2$ lines of code for `let max = 0;` and `return max;`, and then the loop body repeating $3$ times. Okay, but what if our list didn't have three elements, but $100$? Or how about any number, like $n$? Still easy: 2 lines of code for `let max = 0;` and `return max;`, and then the loop body repeating $n$ times (four lines each)-- and for this exact reason, we say that `find_maximum` has time complexity $\Theta(4n + 2)$. That wasn't hard at all! However–we are concerned about what our code does with larger and larger inputs. As out list length $n$ becomes larger, that lonely $2$ will become more and more irrelevant. For that reason, we simply drop it--we say that $n$ is more "dominant" than $2$. We also drop the $4$--if you think about it, we could make that any number, by adding some empty lines in the loop body. Obviously that changes nothing about the performance of the code. Therefor our piece of code has time complexity $\Theta(n)$! If you didn't know, $\Theta$ is pronounced "theta". ## $\Theta(n^2)$ This following code was written by the intern. He doesn't know about $\Theta$ and he said that in his tests, the code perfomed "alright". While it does what it is asked to do, it's less efficient than our code above. Can you see why? ```javascript function find_maximum2(list){ var found = false; for(let x of list) { found = false; for(let x2 of list) { if(x2 > x) found = true; } if (!found) return x; } } ``` The function runs through the list, but for each element, it runs through the list *again*. The inner for loop is $\Theta(n)$, and we do that $n$ times... It's a $\Theta(n \cdot n)$, or $\Theta(n^2)$ algorithm! To see how bad that is, consider a list of length 1000. Our code above needs about a thousand steps to run to completion, while this code needs *a million*. A few lines of code can make all the difference! @plot2@ ## Examples for $\Theta(n^x)$ If you're still with me, nice! You should be able to find the time complexity of lots of your algorithms now. In this section I will hit you with a few more quick exercises for you to figure out. Let's recap quickly: - To figure out the time complexity of an algorithm, run it through in your head and count the number of "steps". - Constant factors will be ignored and only the most dominant term is picked. $\Theta(3n^3 + 4n^2 - n)$ can be "reduced" to $\Theta(n^3)$. - Your gut feeling is usually correct. Armed with that knowledge, try figuring out the complexity of these code samples. When you think you have it, click on the "Show Solution" button. ___ ```javascript function double_and_print(list){ for(let i = 0; i < list.length; i++){ list[i] *= 2; } for(let i = 0; i < list.length; i++){ console.log(list[i]); } } ``` @quiz1@ ```javascript function is_first_element_4(list){ return list[0] == 4; } ``` @quiz2@ ```javascript //print a times table function times_table(n) { for(let a = 1; a <= n; a++){ for(let b = 1; b <= n; b++){ console.log(`${a} * ${b} = ${a * b}`); } } } ``` @quiz3@ ```javascript function print_every_other_number(list) { for(let i = 0; i < list.length; i += 2) console.log(list[i]); } ``` @quiz4@ ```javascript // Uses the times_table function above function lots_of_times_tables(n) { for(let i = 0; i < n; i++) times_table(n); } ``` @quiz5@ ## $\Theta(n^2)$, the sweet-spot of bad optimization As you've probably figured out by now, nested loops are bad. Each nested loop usually adds another factor $n$ to your time, which quickly becomes unmanageable and slow. Sometimes it can't be avoided. Say you are programming a minecraft clone, and you are generating an $n \cdot n \cdot n$ size world--obviously you will have to touch each block at least once, because you want to specify for each block if it is dirt or diamonds. There's just no way to get something faster than an $\Theta(n^3)$ algorithm--it's impossible. ![](https://media.forgecdn.net/avatars/thumbnails/291/283/256/256/637321648723910589.png) But: Many algorithms have easy solutions that are slow, and cleverer solutions that are fast! In programming, we say it's very easy to "$\Theta(n^2)$ yourself": many problems will have very straightforward $\Theta(n^2)$ solutions, and for small $n$ you won't even give a second thought to code performance. Then suddenly, in production, you will encounter $n=100$ or $n=1000$ and your program will come to a grinding halt. $\Theta(n^2)$ is a complexity class that you want to stay away from, if possible, anything above that is usually terrible. To understand what we can do against $\Theta(n^2)$ we need to look at which complexity classes exist *between* $\Theta(1)$ and $\Theta(n)$ and between $\Theta(n)$ and $\Theta(n^2)$. As it turns out, there are complexities other than simple powers and they are the ones we want to be very familiar with. ## Square roots: $\Theta(\sqrt{n})$ Consider this simple primality test: ```javascript function is_prime(n){ if(n % 2 == 0) return false; for (var i = 3; i <= Math.sqrt(n); i += 2) { if (n % i == 0) return false; } return true; } ``` There is a for loop involved, but it doesn't go all the way up to $n$, just to $\sqrt n$. So the time complexity would be $\Theta(\sqrt n) = \Theta(n^{\frac 1 2})$. How does that compare to $\Theta(n)$? @plot3@ Pretty good. ## Logarithms: $\Theta(log~n)$ Logarithms can be tricky to spot, but the basic pattern is repeated division. Here's a $\Theta(log~n)$: ```javascript function do_nothing(n) { let i = n; while(i > 1){ i = i / 2; } } ``` To figure out the time complexity, we are asking "how often do we have to halve to get to $1$?" Let's do some highschool maths, I hope you remember it... %n / 2 / 2 / 2 / 2 / ... = 1% %n / 2^x = 1% %n = 2^x% %log_2~n = x% The answer is $\Theta(log~n)$. Here is a slightly more hidden $\Theta(log ~ n)$ in a more practical code, involving recursion. Can you spot the halving? ```javascript function binary_search(list, value) { let h = Math.floor(list.length / 2); if (list.length === 0) throw "nothing found, sorry :c"; else if (list[h] === val) return h; else if (val > list[h]) return binary_search(list.slice(h, list.length), value); else return binary_search(list.slice(0, h), val); } ``` Usually we are taught that binary searching an array is faster than going through the whole list element by element. Let's see whether that is actually correct: @plot4@ ### Confucius loves logarithms There is the old saying: > For all realistic $n$: $log~n < 40$. Whereas powers will grow faster and faster, $log$ slows down more and more as $n$ gets bigger, to the point where we programmers don't really need to worry about it beyond a certain point. $log~235385266837019970 = 40$... I can't count that high, that's for sure. ### Logarithms and sorting, a.k.a. $\Theta(n^2)$ revisited When you first learn about sorting algorithms, you'll be presented with bubblesort, the easiest sorting algorithm out there. ```javascript function bubble_sort(arr){ for(var i = 0; i < arr.length; i++){ for(var j = 0; j < arr.length; j++){ if(arr[j] > arr[j+1]){ const temp = arr[j]; arr[j] = arr[j + 1]; arr[j+1] = temp; } } } } ``` It's a double for loop, which we can easily identify as $\Theta(n^2)$ by now. As we also know, $\Theta(n^2)$ is slow. Soon after, you will learn about quicksort: ```javascript function partition (arr, l, r) { const pivot = items[Math.floor((l+r)/2)], i = l, j = r; while (i <= j) { while (arr[i] < pivot) { i++; } while (arr[j] > pivot) { j--; } if (i <= j) { const temp = arr[j]; arr[j] = arr[i]; arr[i] = temp; i++; j--; } } return i; } function quick_sort(arr, left, right) { let index; if (arr.length > 1) { index = partition(arr, left, right); if (left < index - 1) quick_sort(arr, left, index - 1); if (index < right) quick_sort(arr, index, right); } return arr; } ``` Explaining the details of sorting algorithms would be out of scope for this tutorial, but we can roughly put them into two categories: - "$\Theta(n^2)$-sort": With a list of size $n$, each element could be at one of $n$ positions. Take each of the $n$ elements and see where it fits. - "$\Theta(n \cdot log~n)$-sort": Take the big pile of numbers and split it in half. Sort these smaller lists (by splitting them in half), and then recombine them. The quicksort code can be tricky if you've never seen it before, but rest assured it is in fact $\Theta(n \cdot log~n)$, which is a big step up from $\Theta(n^2)$. See if you can spot where the halving is taking place. @plot5@ With fast sorting algorithms, many problems that at first seem $\Theta(n^2)$ can be made $\Theta(n~log~n)$. ### Homework! Say we want to write a `group` function that combines like elements in an array, like so: ```javascript group([1,3,3,2,1,1,2,4,3,1]); // result: [[1,1,1,1], [2,2], [3,3,3], [4]] ``` How would you do it? Try to come up with a simple approach that does not involve sorting, and then try to find a solution where you first sort the array using quicksort. Compare the time complexities! ### Logarithm base conversion Here's a small, technical side-note about logarithms. You might be wondering whether $\Theta(log_2~n)$ and $\Theta(log_3~n)$ are different complexity classes, since, just like repeated halving will give you $log_2~n$, repeated division by 3 will give you $log_3~n$. The answer is no. For this we need to dig up some highschool maths again, this time, the logarithm base conversion formula: %log_2~n = log_3~n \left(\frac{1}{log_3~2}\right)% I'm sure you remember that one. As we see, the rightmost term is a constant, about $1.5849$. %log_2~n = log_3~n \cdot 1.5849....% If you recall the very first example in this tutorial, constant factors are ignored. So, as far as $\Theta$ is concerned, all logarithms are created equal: $\Theta(log_2~n) = \Theta(log_3~n)$. As a result, we usually we drop the base when talking about logarithms. Like with quicksort, which is $\Theta(n~log~n)$. ![Drop the base!](https://pbs.twimg.com/profile_images/740718519885520902/DhIwj76Z_400x400.jpg) You can of course keep the base if you would like to be explicit. ## Recap Props if you are still with me. That was a lot! We've seen a many complexity classes by now, and I'd like to take a second to put them all into perspective. We usually put complexity classes into two groups: "Sublinear" and "hyperlinear", meaning, "smaller than $\Theta(n)$" and "larger than $\Theta(n)$", respectively. @plot6@ @plot7@ ## Why is it called big O anyway? I've been talking a whole lot about $\Theta$, but everyone calls it "big O". How come? Mathematicians Bachmann and Landau actually came up with five symbols for describing so-called "asymptotic behaviour": $\Theta$, $\Omega$, $\omega$, $O$, and $o$. I'm not a mathematician myself, but I hear that in maths, $O$ is very common. Sadly there is a misconception in programming where programmers usually *mean* $\Theta$, but say $O$. I suspect it's because nobody can be bothered to type greek letters in everyday conversation. It's fine to be sloppy with notation if everyone is on the same page and knows what you are talking about, but after you've read this tutorial you hopefully know better than most programmers and will use $\Theta$ to talk about time complexity :) To really understand the difference between $\Theta$ and $O$ though, we will need to dig deeper into the maths, which I will do in the next section. ## A formal definition To understand time complexity, you *really* do not need this, this is just for people who are not afraid of maths (calculus) and would like to know a bit more about the topic. You can safely skip this section and will be able to calculate the time complexity for any code you come up with. :) Thanks for reading, now go away! ### A formal definition Okay. I've been saying a lot of nonsense like "constant factors are ignored" and "we pick the most dominant factor" without telling you why and how exactly. Recall for a second the very first example `find_maximum`, and our very first estimate for the time complexity $4n+2$. Then we said that $4n+2$ is in fact $\Theta(n)$. To see whether that's true, we need to divide $4n+2$ by $n$ and see what happens when $n$ gets larger. %\frac{4n+2}{n} = 4 + \frac{2}{n}% What do we mean by "as $n$ gets larger"? We take the limit. %\lim_{n\to\infty} 4 + \frac{2}{n} = 4% The right term tends to zero, and the limit is $4$. This is enough to prove that $4n+2$ is $\Theta(n)$: We require the limit to be larger than $0$, but smaller than infinity. Let's see some complexity classes which $4n+2$ is _not_ inside of: ____ ##### Is $4n+2$ inside $\Theta(1)$? The limit goes to infinity, so no! %\lim_{n\to\infty} \frac{4n+2}{1} = \lim_{n\to\infty} 4n+2 = \infty% ____ ##### Is $4n+2$ inside $\Theta(n^2)$? The limit tends to 0, so that's also a no. %\lim_{n\to\infty} \frac{4n+2}{n^2} = \lim_{n\to\infty} \frac{4}{n} + \frac{2}{n^2} = 0% ____ Intuitively this means that $\Theta(n)$ is all functions that don't "outpace" $n$, and aren't "outpaced" by $n$. ### Notation and nomenclature $\Theta(n)$ is a set of functions. When we say a thing such as "$4n+2$ is $\Theta(n)$", what we mean is that, given functions %f(n) = 4n+2% %g(n) = n% then $f$ is inside the set $\Theta(g)$. To be formally correct, we would need to use proper set theory notation: %f \in \Theta(g)% In practice, nobody does. What I've personally seen most often is %4n+2 = \Theta(n)% which is sloppy but it is what it is. Mathematicians sometimes use $O$ to measure approximations and error terms, and they'll notate it like so: %e^x = 1 + x + O(x^2)% by which they mean $O(x^2)$ to represent any arbitrary element within the set. How is the family of sets $\Theta$ defined? Well, it's simply the collection of functions that fit our limit criteria. %f \in \Theta(g) \Longleftrightarrow 0 < \lim_{n\to\infty}\frac{f(n)}{g(n)} < \infty% ### The other landau symbols The limit in our limit definition of $\Theta$ is bounded on both sides; on the left by $0$ and on the right by $\infty$. $O$ on the other hand is merely an upper bound, so we simply remove the left side: %f \in O(g) \Longleftrightarrow \lim_{n\to\infty}\frac{f(n)}{g(n)} < \infty% What does this mean in practice? Say your teacher asks you to write an algorithm in $O(n^2)$ time; in that case you are still allowed to submit a solution that only needs $n$ steps. $n = O(n^2)$, which would not be true for theta: $n \neq \Theta(n^2)$. This also means that it's valid to say that "bubblesort is $O(n!)$" which is misleading, to say the least. That's why I'm particularly picky about people confusing $O$ with $\Theta$. Anyway, if you were able to handle the limit definitions I just threw at you, I'll refer you [the section in the wikipedia article about big O](https://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann%E2%80%93Landau_notations) for the definitions of the other symbols. It's more of the same basically :) ## And that's it for now! Props if you've made it this far. There is a LOT I have not talked about and I will add more to this document eventually. Please drop a comment if anything is unclear, or if there is anything you would like to see in particular. I hope you got something out of this, and I wish you much luck in your programming studies. Happy coding!

Big O tutorial