What is Big O?
Recently, a friend asked me if I knew what big O notation was. I had never heard of the thing before, so I decided to do some reading and condense what I learned here. They say teaching is the best way to learn, so here we go, and hold on to your… well, seats!
Big O notation is used in computer science to describe how complex an algorithm is. In particular, we are concerned with how much time it will take to run the algorithm based on what we feed into it. This is important because that will help to compare the speed of different algorithms so we can decide which will be the best solution to the problem. Another way to think about it is, big O notation describes how well an algorithm scales. How quickly will the algorithm handle the problem as the amount of data increases?
Wait, but what is an algorithm? I can’t hear or read the word algorithm without thinking about Star Trek: Voyager and its all-too-frequent use of pseudo-scientific terms like “Borg algorithm”. I can imagine Seven of Nine furiously tapping away at a computer console and saying, “I am using a Borg algorithm to [insert random plot element here].” It really seemed like they threw the term around whenever they needed to do something unusual with the computer. To its credit, though, Voyager used the word algorithm generally correctly to conceptually describe a distinct collection of computer code that accomplished a specific task.
So, besides overriding a Starfleet security clearance, what would you use an algorithm to do, and why is big O helpful in understanding that algorithm? Searching for a piece of data is a common task that can be accomplish with algorithms. Big O notation describes how long it might take the algorithm to find that piece of data or how many times it might have to go through the data set to find it. I say might because big O notation describes the worst-case scenario. When we search for something, by definition, we don’t know where the item is. The algorithm that is searching for it could find the data almost immediately, or it may not find it until it gets to the end of the data set. A simple way to think about this is to imagine you are looking for the Ace of Spades in a pile of five cards. It could be the first card you turn over, or you might have to turn over all five cards before you find it. Basically, big O will tell you how long it will take you to find the Ace if it is the last card in the deck.
Using this example, then, lets jump into some examples.
Common Types of Big O Notation
Big O notation is written as an equation beginning with a capital “O” followed by some kind of multiplier. For example: O(1). When we use it to describe an algorithm, we say that it is, “an order of 1.”
O(1)
An algorithm with an order of 1 always performs the same regardless of size of data. Going back to our deck of cards, this would be like finding the first card in a deck. No matter how big the deck is, the time needed to complete the search is always the same.
O(n)
An algorithm with an order of n is directly proportional to the data that is passed into it. This would be like looking for the 2 of Hearts. A search through a deck of 200 cards would take twice as long as a search through 100 cards. It is possible that the card could be found after going through 53 cards or even 5 cards. But, again, big O notation describes the worst-case scenario.
O(n^2)
An algorithm with an order of n^2 describes an algorithm that will become exponentially slower and less efficient as the data increases. This type of algorithm would contain a loop that would go through all of the data and then repeat the process all over again for each point in the data set.
This is a somewhat more complex situation, but imagine that within a deck of cards in which there are only two cards that are the same. How would you find the duplicate pair? How would you search for the cards if you could only look at two cards at once? An algorithm with an order of n^2 would take the first card off the top of the deck, turn it face up, and set it aside. Then it would take the second card, turn it face up, and compare it to the first. If the cards don’t match, it would turn that second card over and set it in a discard pile. Then it would take the third card and so on and so forth until it reached the end of the deck. If no match was found, it would take the second card, turn it face up, and start the comparison process for the entire deck all over again.
You can see how quickly this can become an arduous task. If you have a deck of 5 cards, you would have to turn over 25 cards. If you had a deck of 10 cards, you would have to turn over 100 cards! Granted, computers can do this very fast. But imagine you were working with data sets of a million or even a billion records. At these sizes, speed and efficiency become increasingly important.
O(log n)
An algorithm with an order of log n is much more efficient. In fact, it is even more efficient than O(n). An algorithm of this type would break the data into half thereby drastically reducing the amount of work it has to do. The larger the data set, the greater the benefit of the initial divisions.
Let say that we are looking for the Queen of Spades in a deck that is sorted by card value. We don’t know the exact position of the Queen. Out of 52 cards, is it card 39? Is it card 46? An algorithm with an order of log n would cut the deck exactly in half and look at the card. If the card is lower in order than the Queen, it would take the higher half and cut it in half again. This process would repeat until the Queen of Spades is found. In a 52 card deck, you would cut the deck in half a maximum of 5 times to find the one you want.
Algorithms of this type are extremely good at handling huge amounts of data. Doubling the size of the data has very little effect, because it only adds a single step for the algorithm.
The End
Hopefully that made sense to you. What did you think of this article? Was it helpful? Was it absolutely atrocious? Let me know in the comments below.