Let’s cut to the chase—a lot of the interest and initial motivation around learning Big O stems from its prevalence in technical interviews.
Employers want to confirm that prospective employees understand the main concepts of Big O because the notation provides detail and specificity to the language we use when comparing and discussing the behaviors of different implementations of data structures and algorithms.
In this article:
- A beginner's introduction to Big O (not including Big Theta or Big Omega)
- Examples to help understand time complexity
- An exploration of how Big O notation offers a more precise vocabulary when comparing data structures and algorithms
The O in Big O
Big O notation, or Landau’s symbol, is used in computer science to describe the asymptotic behavior of functions—or, more easily phrased, Big O expresses how the runtime or some other performance metric of an algorithm changes in relation to the size of its input.
The notation is named after its inventor: the German number theoretician Edmund Landau, and the letter O refers to the functions rate of growth, also known as its order [1].
Why is Big O important?
Big O is considered the primary metric used to describe the efficiency of algorithms [2].
The beauty of software engineering is that it incorporates both art and science. It is artistic in the sense that abstracting different concepts into code can be considered as a form of creative expression yielding endless ways of crafting programs to perform a task.
Given this understanding, our opinions towards different ways of implementing code become difficult to frame under a strict right vs wrong categorization. Instead, it is more accurate to consider certain data structures and algorithms as being more advantageous than others given a certain context.
Difficulties of consistently measuring performance
Performance, or how much time, memory, and disk space being used when a program is run is influenced by many factors, including the machine specifications, the compiler, the language the code is written in, and of course, the code itself [1].
This makes it hard to reproduce consistent results, and therefore even harder to deduce valid and more importantly, generalizable correlations between an algorithm’s implementation and its performance.
LeetCode Two Sum example:
Time Complexity = O(n2)
const twoSumTwoNestedIf = (nums, target) => {
for (let i=0; i < nums.length -1; i++){
let solution = target - nums[i];
for(j=nums.length - 1; j > i; j--){
if( solution === nums[j] ){
return [i,j]
}
}
}
return null;
}
Time Complexity = O(n)
const findTwoSumRefactored = (nums, target) => {
const numsMap = {};
for(let p=0; p<nums.length; p++) {
const currentMapVal = numsMap[nums[p]];
if(currentMapVal >= 0) {
return [currentMapVal, p];
} else {
const numberToFind = target - nums[p];
numsMap[numberToFind] = p;
}
}
return null;
}
let numberArray = [2,7,5,11]
let targetValue = 9
let startTime1 = performance.now();
console.log(findTwoSumRefactored(numberArray, targetValue))
let finishTime1 = performance.now();
let time1 = (finish1 - start1)/1000
console.log(`Time elapsed for findTwoSumRefactored: ${time1} seconds`)
let startTime2 = performance.now();
console.log(twoSumTwoNestedIf(numberArray, targetValue));
let finishTime2 = performance.now();
let time2 = (finish2 - start2)/1000
console.log(`Time elapsed for twoSum: ${time2} seconds`);
For example, when we use performance.now() to provide a rough estimate for the time taken to run our code we experience inconsistent outputs even when using the same machine.
Although the margins of performance may vary when measuring our code, the relationship between a function’s time or space complexity to the size of input does not. For this reason, we analyze our code in terms of its complexity, or how the resource requirements of a program or algorithm scale.
Simplifying relationships with Big O for a high-level understanding
Many mathematicians and more seasoned programmers may take umbrage with this statement, but with Big O we do not have to care about the details of our algorithms as much as the relationships between them. When analyzing the Big O time complexity of an algorithm, the focus is primarily on how the code behaves with different sized inputs.
It is common to imagine the worst-case scenario to benchmark our algorithm, or resort to its asymptotic growth rate. By imagining a scenario where the input size approaches infinity, we ignore less significant factors impacting our algorithm and focus solely on the high-level complexity.
We can also treat variable assignment, arithmetic operations, and accessing an array's value by index or an object's value by key all are considered as having constant time.
Big O is not concerned so much about precision as much as general governing trends. For that reason, we ignore constants O(450) => O(1) | O(8n2) => O(n2) and smaller mathematical terms O(850n + 400) => O(n).
Loops, however, have a complexity proportional to the length of the loop's iterations multiplied by whatever happens inside the loop. Nested loops frequently exhibit quadratic growth--each iteration for the outer loop also entails an inner loop running n times as well.
Reflecting upon the different approaches for the LeetCode Two Sum question, we see that both exhibit polynomial Big O growth, where the dynamic element impacting the time complexity pertain to the base n, yet the two pointer solution does not scale as well as the refactored implementation, in terms of time complexity.
TL;DR:
Big O notation is a formalized way of talking about how the runtime of an algorithm changes in relation to the growth of its input size. This approach focuses on the complexity of the algorithm, helps isolates inconsistent contributing factors when measuring our codes effectiveness, and provides needed context when comparing algorithms. Generally speaking, Big O notation and the descriptions we derive from it serve a similar purposes to the Richter Scale’s incremental gradation of earthquake severity--you may not have to fully understand how it is derived to glean some pretty helpful insights, but the deeper the understanding the better!
References
[1] “Big O notation.” web.mit.edu/16.070/www/lecture/big_o.pdf (September 8, 2023).
[2] G.L. McDowell. “Cracking the Code Interview.”6th Edition. Palo Alto, California, USA. CareerCup, 2016.