Computer Science for people who hate math — Big-O notation — Part 1
Oh, the Big-O.
We have to start somewhere and Big-O notation is a core part of understanding why data structures and algorithms matter. It’s also one of those pieces of jargon that you will hear pretty early on in your career, either in a technical interview or in conversation with your colleagues. Unfortunately it is often not explained very well for those of us who don’t have math as a second language.
So before we start delving into all the details of Big-O notation, we’re going to start with the basics.
What’s a data structure again?
A data structure is just a way of organizing your data with rules about what you can do with that data. For example, a data structure might have rules such as:
- how to access it,
- how to modify it, and
- how each value in your data relates to other values in that same data
Remind me what you mean by “algorithm”
An algorithm is just a series of steps for how to get from state A to state B. It’s not just a computer term — there’s (many) algorithms for making the perfect cup of tea, for example.
Why is it called “Big O”?
Funny how no-one ever really explains this unless you go digging around in some of the more mathematical explanations. Here’s my simplified explanation:
The “O” stands for “order of the function”. This is NOT some medieval round-table staffed by the Knights of the Order of the Mathematicians. Instead it’s just a fancier way of saying “the growth rate of a function”.
What is the Big Deal with Big O?
It’s pretty simple. Even though computers are very fast, it still makes sense to be mindful of how efficient your software is. If nothing else, making a computer do a whole bunch of additional, unnecessary operations uses energy — and it slows your software down. So, make your software greener and more performant (yes that’s a real word in the software world) by doing things as efficiently as possible.
Okay, but you didn’t really answer my question.
I’m getting there! Big-O notation is a way of dividing problems up into how well they perform in a worst case scenario. It does this by looking at how many steps an algorithm takes and how the number of steps grows with the number and size of inputs you give it.
Another way of defining Big-O notation is that it is a way of comparing the time complexity (or rate of growth of different programmatic approaches AKA “algorithms”) to output the result we want given the same set of inputs. So it’s the growth rate of your function as it relates to the size of the inputs.
Can you break this “time complexity” thing down a little bit more for me?
Of course! Complexity is the number of operations (or steps) an algorithm has to do to output the desired results from the inputs provided. The time portion relates to how long the algorithm takes as the number and/or size of the input(s)s increases. Time complexity combines both of these concepts into the idea that as the size of the input increases, the number of steps may either not increase at all, increase in lock-step with the size/number of inputs, or may increase at some rate that is higher than the increase in the inputs (such as every additional one input requires two additional steps).
Isn’t this really just a fancy way of saying how long something is going to take?
Good point, it is, pretty much. But remember that something can run very slowly on an old computer, and very quickly on a supercomputer. So talking about efficiency in terms of rate of growth is a better way of defining how efficient an algorithm is without getting hung up on things like what hardware we were running it on, or other irrelevant factors.
Real Life Example
Let’s look at a real life example to understand the whole Big-O thing a bit better.
Suppose you’ve decided to reorganize and downsize your books. You have five shelves of books and you have decided to replace at least some of them with eBooks.
- First you need to clear some space on the floor to work on.
- Then you’ll need to pull all the books off the shelf so you can decide what you no longer want.
- Finally, while you’re at it, you might as well reorganize the books into alphabetical order.
Step one: Clearing the floor space
Whether you have five short shelves that hold only 20 books each (a total of 100 books), or five really long shelves that hold 100 books each (a total of 500 books), clearing some space on the floor to work on is going to take the same amount of time because it’s always going to be the same number of steps. No matter how small or large your book collection happens to be, you’re still going to be moving two chairs, a coffee table, and one beanbag.
So we can say that clearing the floor space is something that takes a constant number of steps, no matter how many books we’ve decided to sort out this weekend. In Big-O notation, when we talk about something that takes a constant number of steps, no matter how large the input is, we represent it like this: O(1). ← See! Our first bit of math, and it’s not all that hard!
Remember that the O just means “Order of the function” which itself simply means “rate of growth”. So all O(1) means is that the rate of growth is “1”. Don’t take this too literally — it might actually be two or three steps or more. The important thing here is that the “1” is representing a constant.
Step two: Get the books off the shelves
Okay, so you could technically do this in just one step, but let’s assume that you don’t want your books to get too beat up by just yanking them all off the shelf in one go. So instead you decide to pull them off one by one and put them in an organized pile somewhere.
Pulling them off one by one means that if you have 100 books, you’ll repeat that set of steps 100 times. But if you have 5000 books, you’ll do it 5000 times (at which point you might decide to go clean the bathroom instead).
So we can say that getting the books off the shelves is something that will take an amount of time that increases in a linear fashion. This linear relationship — where for a given number of books (represented by “n”), we increase our repetition of the steps involved in pulling each book off the shelf by the number of books — is represented by O(n). So in this case the rate of growth is “n” — the total time it takes to get the books off the shelves goes up in lockstep with the total number of books.
Let me be a little more concrete about this one. Suppose every book takes the same amount of time — maybe 5 seconds — for you to get off the shelf. For one book it will take 5 seconds to complete the entire task. For two books it will take 5 seconds for each book, for a total of 10 seconds. For three books it will still take 5 seconds for each book, for a total of 15 seconds. So the total amount of time will always be five seconds multiplied by the total number of books you pull off the shelf.
The time goes up in this linear way because it doesn’t matter how many books we have — we will only ever have the same number of steps (and time) needed per book to get it off the shelf and onto the floor.
Step three: Reorganize the books
Ah, now this is where it gets a little tricky, because depending on exactly how we choose to reorganize the books, we could be doing it really inefficiently, or really efficiently. So this one we’re going to revisit in a later post when we talk about sorting.
What’s next?
First: Was this helpful? Was there anything you didn’t understand? And for those of you that are mathematically talented, is there anything you think I over-simplified or simply got wrong? Leave comments to let me know!
Second: We’re going to talk about sorting (and a little bit about data structures) so we can think about how to reorganize these books we’ve got scattered all over the floor. My next article in this series will look at two (or maybe more!) sorting algorithms so we can start to understand why it’s important to think about efficiency. We’ll also look at how Big-O notation helps us think about the efficiency of algorithms in a structured, helpful way so we don’t have to just “go with our gut feeling”.
