What Is Big-O Notation?
Big-O notation gives you a way to calculate how long it will take to run your code. You can physically time how long your code takes to run, but with that method, it is hard to catch small time differences. For example, the time it takes between running 20 and 50 lines of code is very small. However, in a large program, those inefficiencies can add up.
Big-O notation counts how many steps an algorithm must execute to gauge its efficiency. Approaching your code in this manner can be very effective if you need to tune your code to increase efficiency. Big-O notation will enable you to measure different algorithms by the number of steps it requires to run and objectively compare the algorithms’ efficiency.
How Do You Calculate Big-O Notation
Let’s consider two functions that count how many individual socks are in a drawer. Each function takes the number of pairs of socks and returns the number of individual socks. The code is written in Python, but that does not affect how we would count the number of steps.
def sockCounter(numberOfPairs): individualSocks = 0 for x in range(numberOfPairs): individualSocks = individualSocks + 2 return individualSocks
def sockCounter(numberOfPairs): return numberOfPairs * 2
This is a silly example, and you should be able to easily tell which algorithm is more efficient. But for practice, let’s run through each.
If you’re learning how to program your own code, you’ll need to understand what functions are.
Algorithm 1 has many steps:
- It assigns a value of zero to the variable individualSocks.
- It assigns a value of one to the variable i.
- It compares the value of i to numberOfPairs.
- It adds two to individualSocks.
- It assigns the increased value of individualSocks to itself.
- It increments i by one.
- It then loops back through steps 3 to 6 for the same number of times as (indiviualSocks – 1).
The number of steps we have to complete for algorithm one can be expressed as:
4n + 2
There are four steps that we have to complete n times. In this case, n would equal the value of numberOfPairs. There are also 2 steps that are completed once.
In comparison, algorithm 2 just has one step. The value of numberOfPairs is multiplied by two. We would express that as:
If it wasn’t already apparent, we can now easily see that algorithm 2 is more efficient by quite a bit.
Generally, when you are interested in the Big-O notation of an algorithm, you are more interested in the overall efficiency and less so in the fine-grain analysis of the number of steps. To simplify the notation, we can just state the magnitude of the efficiency.