A series where I introduce concepts in programming ranging from data structures to algorithms to programming languages.
In the first part of this series we introduced Binary Search. It was a simple algorithm that searches for an item in a sorted list by starting at the middle and continuously cutting the list in half until we reach our item.
That was one of the first algorithms I learned, but what exactly is an algorithm? This word is thrown around so often it’s hard to get its definition from context clues. To me, an algorithm is a set of instructions that is given to a computer to solve a particular problem. In the binary search example, the problem is to find an item in a sorted list.
When creating an algorithm for a problem, the processing power of the computer should be considered. You might create an amazing algorithm, but what use is it if your computer can’t even run it? How do we compare algorithms to determine an efficient one? This is where Big O notation comes in.
Big O Basics
Unfortunately because computers have different processing power, we can’t rely entirely on the run time of algorithms as it may differ. However, what won’t change from computer to computer is the amount of operations an algorithm has to perform to reach its solution. This is essentially what Big O notation compares, the amount of operations an algorithm performs and how well that scales with increasing input.
What does Big O Notation look like?
Now that we know what Big O Notation is and what it shows, how do we write it? The expression is fairly simple:
The expression starts with a big “O” and then inside the parenthesis you put the number of operations for that specific algorithm, so this expression is subject to change based on the algorithm. The algorithm we talked about previously in this series, Binary Search, has Big O notation of O(log n), also known as log time. So now we know what Big O is and how to express it, we need to figure out how to determine the number of operations an algorithm takes to solve its problem.
This will not be a comprehensive guide on determining Big O notation for every single algorithm you create, but we’ll talk about a way to gain an intuition for how an algorithm scales.
The big idea that really got Big O notation to click in my head is, how much of the input does our algorithm touch. Let’s take an example of simple search, where you search through an input by starting at the first item and moving your way through every item. If this input has 100 items, in the worst case scenario you’d have to check every item in the input. If the input had 1,000 items, in the worst case scenario you’d have to search through 1,000 items. If the input had 1,000,000 items, you guessed it, you’d have to search through all 1,000,000 items in the worst case. This is an algorithm that operates in linear time, the amount of operations is directly proportional to the input. Determining the amount of operations for other algorithms such as Binary Search isn’t as intuitive and does require a bit of mathematical manipulation which is out of the scope of this introduction. There are many other algorithms with different Big O notation which we’ll look at very quickly.
Big O notation for other Algorithms
Below is a chart to show possible time complexities and where they fall on a terrible to amazing scale.
We’ve already seen one of the Big O notations already, O(log n) (Binary search) and O(n) (Simple Search). There are some algorithms out there that scale very poorly to the number of elements given to them as inputs. An example of each of these can be:
- O(log n) : Binary Search
- O(n) : Simple search
- O(n * log n) : Quick Sort
- O(n ^2) : Selection Sort
- O( n!) : Travelling salesperson
These are some examples of the big O complexities found in the chart and there are many more. I encourage you to take a look at these different algorithms and try to figure out how to deduce their Big O notation.
We’ve covered some of the basics on Big O notation. I’ve barely scratched the surface with Big O notation so I encourage everyone reading this to delve deeper into it. Big O is an important concept in programming and quite a scary one too. It took me a very long time to become comfortable with it and I think anyone who is learning programming should have this soft introduction to it first before learning about how to calculate Big O notation for every single algorithm. Next time we’ll talk about Recursion!