Understanding Big O Notation for the Newbie Dev
What is Big O Notation?
Big O Notation is a consistent way to measure the complexity (time and space) of your code. You may be familiar with different ways to benchmark your code using time as a reference point. The problem with benchmarking with time alone is that the outcome will vary based on the machine used to run the code.
For example, running one million iterations on a supercomputer versus your mac will yield much different results. Even running the same piece of code multiple times on your machine will yield different results depending on the resources available to your computer at the time of execution.
So, enter Big O Notation. With Big O Notation, we measure the number of simple operations your code executes. Simple operations include things like assignments, looping and arithmetic operations.
An example would be:
addNumbers = (n) => {
return n * (n-1) / 2
}First, we represent Big O Notation by writing O(something). The above code has three arithmetic operations. So, we’d write O(3).
Here’s another example:
addNumbers = (n) => {
let t = 0
for (let i=0; i<=n; i++) {
t += n
}
return t
}At first glance, the total number of operations is 6. You may be tempted to write O(6), however, we have to take into account that this code has a for loop. How many iterations the for loops runs is dependent on how big the initial value of n is. So, we’d write this as O(6n).
Simplifying Your Notation
The goal of Big O is to give a general idea about the time and space complexity of your code. When thinking about how to calculate your code’s Big O Notation, think in terms of millions of iterations. Does the complexity increase marginally, linearly or exponentially?
I’m going to gloss over the log values for Big O Notation for now. I want you to just familiarize yourself with the idea of the code complexity being constant O(1), linear O(n) or quadratic O(n²).
So, in writing Big O Notation, we ignore constants as they have a small impact on the overall complexity. What then can be considered a constant?
Shorthand to Determining Big O Notation
1) Arithmetic operations are constants: (+, -, *, /)
2) Variable assignments are constants
3) Accessing elements in array by index or by key in object are constants
4) In a loop, the complexity is the length of the loop times the complexity of whatever happens inside the loop
And, when writing Big O Notation, we remove the constants. So, let’s revisit our above examples.
addNumbers = (n) => {
return n * (n-1) / 2
}We’d simplify this from O(3) to just O(1).
addNumbers = (n) => {
let t = 0
for (let i=0; i<=n; i++) {
t += n
}
return t
}We’d simplify this from O(6n) to just O(n).
And, here is an example of a quadratic relationship.
findAllPairs = (n) => {
let arr = []
for (let i=0; i<=n; i++){
for (let j=0; j<=n; j++){
arr[i][j]
}
}
return arr
}Because we have a nested loop, the total iterations grows by n^2. So, we write the Big O Notation as O(n²).
Difference Between Time and Space Complexity
In the above examples, I’ve been implicitly referring to the time complexity of each code snippet. But, it is important to understand that a piece of code will have two Big O Notations; one for its time complexity and one for its space complexity.
Time complexity refers to the code’s execution speed and space complexity refers to how much memory the code uses. Take an array for example. Time complexity is how long it takes to loop through the array and space complexity is how much memory is needed to store all the values in the array.
Let’s see a code example:
printArr = (arr) => {
for (let i=0; i<arr.length; i++){
console.log(arr[i])
}
}Time complexity: O(n) | Space Complexity: O(1)
doubleArr = (arr) => {
let t = [];
for (let i=0; i<arr.length; i++){
t.push(arr[i]*2)
}
return t
}Time Complexity: O(n) | Space Complexity: O(n)
In the first example, we’re just looping through an array and printing its values — nothing is being stored. In the second example, we’re building a new array as we iterate, which increases the code’s space complexity.
Big O Notation of Logarithms
As mentioned above, a basic understanding of Big O Notation denotes whether the code’s complexity stays constant or increases at a linear or exponential rate. A code’s complexity can also increase at a logarithmic rate. The logarithmic rate is determined by how many iterations it takes to bring a value to 0.
Logarithms are the inverse of an exponent, just like multiplication is the inverse of division.
Here’s the formula:
logBase(value) = exponent is the inverse of Base^exponent = value
So, log2(8) = 3 is the inverse of 2³ = 8.
In mathematics, a log of a number must have a base. However, in Big O Notation we can omit the base because on a large enough time scale, the base becomes irrelevant.
So, in calculating the Big O Notation, we’d write O(log n ) or O(nlog n). Logs usually come into play when dealing with searching algorithms. Instead of looking through the components one by one, they split the data in chunks and discard a large amount on every iteration, usually the half, or log base 2.
Interesting Notes
Remember, have multiple for loops is much better than have a single nested for loop. Take the following example:
findAllPairs = (n) => {
let arr = []
for (let i=0; i<=n; i++){
for (let j=0; j<=n; j++){
arr[i][j]
}
}
return arr
}If n is 100, the total iterations will be 10,000 (100x100).
Now, look at an example with two separate for loops.
printAndAddNumbers = (arr) => {
for (let i=0; i<=n; i++) {
console.log(arr[i])
}let t = 0
for (let i=0; i<=n; i++) {
t += arr[i]
}return t
}
If arris 100. The total iterations will be 200 (100+100). Remember, constants don’t count, so even though this is O(2n), we’d simply write O(n).
The main takeaway is that nested loops should be avoided if possible as they have a Big O Notation of O(n²).
