What is O(๐)? Learn Big O Quadratic Time Complexity
Jared Nielsen Updated on ใป8 min read
Is there a computer science topic more terrifying than Big O notation? Donโt let the name scare you, Big O notation is not a big deal. Itโs very easy to understand and you donโt need to be a math whiz to do so. In this tutorial, youโll learn the fundamentals of Big O notation quadratic time complexity with examples in JavaScript.
This is the fourth in a series on Big O notation. If you want to stay in the loop, sign up for my weekly newsletter, The Solution.
What Problem(s) Does Big O Solve?
- Big O notation helps us answer the question, โWill it scale?โ
- Big O notation equips us with a shared language for discussing performance with other developers (and mathematicians!).
Quick Refresher
In the first twp parts of this series, we looked at constant and linear time complexity, or O(1) and O(n). If youโre just joining us, you will want to start with that article, What is Big O Notation?
What is Big O?
Big O notation is a system for measuring the rate of growth of an algorithm. Big O notation mathematically describes the complexity of an algorithm in terms of time and space. We donโt measure the speed of an algorithm in seconds (or minutes!). Instead, we measure the number of operations it takes to complete.
The O is short for โOrder ofโ. So, if weโre discussing an algorithm with O(n^{2),} we say its order of, or rate of growth, is n^{2,} or quadratic complexity.
How Does Big O Work?
Big O notation measures the worst-case scenario.
Why?
Because we donโt know what we donโt know.
We need to know just how poorly our algorithm will perform so we can evaluate other solutions.
The worst-case scenario is also known as the โupper boundโ. When we say "upper bound", we mean the maximum number of operations performed by an algorithm.
Remember this table?
O | Complexity | Rate of growth |
---|---|---|
O(1) | constant | fast |
O(log n) | logarithmic | |
O(n) | linear time | |
O(n * log n) | log linear | |
O(n^{2)} | quadratic | |
O(n^{3)} | cubic | |
O(2^{n)} | exponential | |
O(n!) | factorial | slow |
It lists common orders by rate of growth, from fastest to slowest.
We learned O(n), or linear time complexity, in Big O Linear Time Complexity. Weโre going to skip O(log n), logarithmic complexity, for the time being. It will be easier to understand after learning O(n^{2),} quadratic time complexity.
Before getting into O(n^{2),} letโs begin with a review of O(1) and O(n), constant and linear time complexities.
O(1) vs. O(n): Constant and Linear Time Complexities
The following function finds the sum of an array of numbers.
const nums = [1,2,3,4,5,6,7,8,9,10];
const sumHarder = arr => {
let sum = 0;
for (let i = 0; i < arr.length; i++) {
sum += arr[i];
}
return sum;
}
const result = sumHarder(nums);
Whatโs the Big O?
O(n).
Why?
Itโs rate of growth scales in direct proportion to the input. As the input grows, so do the number of operations, linearly. Our function needs to perform the same number of operations for every input, so its time complexity is linear, or O(n).
Can we do better?
We learned in How to Sum Integers 1 to n a party trick discovered by Little Carl Friedrich Gauss:
n ( n + 1 ) / 2
If we translate this equation to JavaScript:
const sumSmarter = arr => arr.length * (arr.length + 1) / 2;
Whatโs the order of our function now?
O(1), or constant time.
Why?
Regardless of the size of the input, our algorithm will perform the same, or, a constant number of operations.
Math OโClock ๐งฎ ๐
"Quadratic" is the fancy adjective used to describe squaring, or raising to the power of 2.
Itโs from the Latin quadrus, which means, you guessed it, square.
Whatโs a square in math?
The square of a number is the result of the number multiplied by itself.
Two to the power of two, or 2^2
, is the same as 2 * 2
, or 4.
Three to the power of 2, or 3^2
, is the same as 3 * 3
, or 9.
You know this already.
If we chart quadratic equations, we get a parabola:
Weโre only concerned with the right-side, or positive, values of our parabola because we canโt go back in time.
Yet.
Speaking of time, Math O'Clock is over.
Back to Big O.
O(n^{2):} Quadratic Time Complexity
If an algorithm is in the order of O(n), or linear time complexity, the number of operations it performs scales in direct proportion to the input.
What if an algorithm is O(n^{2)?}
๐ The number of operations it performs scales in proportion to the square of the input.
Whatโs happening in this example?
const fruit = ["๐", "๐", "๐", "๐", "๐", "๐", "๐", "๐", "๐", "๐"];
const matcher = array => {
for (let i = 0; i < array.length; i++){
for (let j = 0; j < array.length; j++){
if (i !==j && array[i] === array[j]){
return `Match found at ${i} and ${j}`;
}
}
}
return 'No matches found ๐';
}
We declare an array of fruit and pass it to our matcher()
function. Our matcher()
function then iterates over our array. For each element in the array, we then iterate over the array again. If the array indices are not the same and the elements at the indices are the same, then we return the locations of the matched fruit. If no matches are found, we return disappointment.
How many operations are performed?
Our outer loop is performing n iterations. Our inner loop also performs n iterations. But it performs n iterations for every iteration of the outer loop.
When i
is 0, we iterate j
10 times.
When i
is 1, we iterate j
10 times.
Etc.
Rather than O(n) or O(n + n), this is O(n * n), or O(n^{2).}
At this point, we are familiar with the following: O(1), O(n), and O(n^{2).} For comparison, this table outlines their growth by number of inputs:
Big O | # operations for 10 elements | # operations for 100 elements | # operations for 1000 elements |
---|---|---|---|
O(1) | 1 | 1 | 1 |
O(N) | 10 | 100 | 1000 |
O(N^{2)} | 100 | 10000 | 1000000 |
As we can see, O(n^{2)} isnโt great to begin with and only gets worse as the size of the input increases.
Remember this chart?
As we can see, O(n^{2)} is horrible.
But itโs not the worst!
Calculating Complexity
The following are common pitfalls and gotchas when calculating Big O quadratic time complexity.
Drop Non-Dominant Terms
Whatโs happening in this contrived example?
const summer = (num, t = false) => {
let sum = 0;
if (t === 'quadratic'){
for (i = 0; i <= num; i++){
for (j = 0; j < num; j++){
sum += j;
}
}
} else if (t === 'linear') {
for (i = 0; i <= num; i++){
sum += i;
}
} else {
return num * (num + 1) / 2;
}
return sum;
}
If our first condition is met, we run the nested iterations and the order of our function is O(n^{2).}
If our second condition is met, we run one iteration and the order of our function is O(n).
If neither of the conditions are met, our function is O(1).
What is the actual order of our function?
We could calculate this as O(n^{2} + n + 1).
Why would we not do this?
When using Big O to measure the rate of growth of our algorithms, what do we really want to know?
We want to know the worst-case scenario.
Here, itโs n^2
.
This is the dominant term.
We learned earlier that we drop constant terms.
We also drop n
, the non-dominant term, because it doesnโt provide any meaningful additional information. Whether or not n
influences the rate of growth of our algorithm is irrelevant. With or without it, our algorithm is still quadratic.
What we really want to know is the order of our function, not the details of its specific implementation. So the example above is O(n^{2).}
Iteration with Offset
What happens if we make a small optimization to our matcher()
algorithm?
const fruit = ["๐", "๐", "๐", "๐", "๐", "๐", "๐", "๐", "๐", "๐"];
const matcher = array => {
for (let i = 0; i < array.length; i++){
for (let j = i + 1; j < array.length; j++){
if (array[i] === array[j]){
return `Match found at ${i} and ${j}`;
}
}
}
return 'No matches found ๐';
}
If weโre checking for a match, we know that it will never be in the same index in the array.
We can initialize the inner loop with let j = i + 1
, so the iterator of the inner loop will always be one element ahead of the outer loop.
This allows us to remove the i !== j
operation in the if
statement.
Here's the catch: how many times will the inner loop, j, run?
Letโs make a table!
i | j | number of iterations of j |
---|---|---|
0 | 0 + 1 | 5 - 1 = 4 |
1 | 1 + 1 | 5 - 2 = 3 |
2 | 2 + 1 | 5 - 3 = 2 |
3 | 3 + 1 | 5 - 4 = 1 |
4 | 4 + 1 | 5 - 5 = 0 |
Total: 10 |
Letโs say we have an array with five elements. When the value of the iterator in our outer loop, i, is 0, the value of the iterator in our inner loop, j, is the value of i plus 1. As the value of i increases, the number of iterations performed by j decreases correspondingly.
What if our array length is variable, or, unknown? How would we calculate the number of iterations of our inner loop?
i | j | number of iterations of j |
---|---|---|
0 | 0 + 1 | n - 1 |
1 | 1 + 1 | n - 2 |
2 | 2 + 1 | n - 3 |
... | ... | ... |
n - 3 | n - 3 + 1 | 2 |
n - 2 | n - 2 + 1 | 1 |
n - 1 | n - 1 + 1 | 0 |
The first time our outer loop runs, our inner loop runs n - 1
.
The second time our outer loop runs, our inner loop runs n - 2
.
The third time, n - 3
.
Hey! This is starting to look familiar. Where have we seen this pattern before?
It's very similar to summing consecutive integers from 1 to n.
We can calculate this with the following equation:
n * ( n - 1 ) / 2
We can simplify this mathemagically.
While itโs not exactly square, recall that in Big O, weโre not interested in the details. So we drop the constants and multiply the terms with a result of n^{2}.
Letโs visualize it: imagine a function that logs the pairs of i and j, with an output of the following:
[
[ [ 0, 1 ], [ 0, 2 ], [ 0, 3 ], [ 0, 4 ] ],
[ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ] ],
[ [ 2, 3 ], [ 2, 4 ] ],
[ [ 3, 4 ] ]
]
See a pattern?
It's half a square matrix.
We could write that as:
( n * n ) / 2
If we drop the constant, the divisor, itโs just n^{2}.
In Cracking the Coding Interview, Gayle Laakmann McDowell directs us to think about what the code means.
What does that mean?
Our function is comparing pairs, i and j.
The total number of pairs to compare is i * j, or, because we are using the same input, n * n, or n^{2}.
But! We are only comparing pairs where j is greater than i, which is approximately half of the total number of pairs.
We will never compare pairs where j is less than i.
Again, we can write this as:
( n * n ) / 2
And again, if we abstract away the details, itโs O(n^{2).}
Two Inputs
What if our function accepts two inputs of varying, indeterminate length?
const matcher = (arr1, arr2) => {
for (let i = 0; i < arr1.length; i++){
for (let j = 0; j < arr2.length; j++){
if (arr1[i] === arr2[j]){
return `Match found at arr1[${i}] and arr2[${j}]`;
}
}
}
return 'No matches found ๐';
}
Is this O(n^{2)?}
Only if both arrays are equal in length, or n.
Because we donโt know what we donโt know, we need to treat each value separately.
So this is O(n * m).
In mathematics, this is known as a multilinear function. Bust that out in your next technical interview!
Big O Quadratic Time Complexity
Does O(n^{2)} scale?
We can do worse.
We can definitely do better.
Weโll see how in the next tutorial.
In this tutorial, you learned the fundamentals of Big O quadratic time complexity with examples in JavaScript. Stay tuned for part four of this series on Big O notation where weโll look at O(log n), or logarithmic time complexity. If you want to stay in the loop, sign up for my weekly newsletter, The Solution.