Big O notation is a mathematical shorthand used in programming to describe the worst and based case scenarios of any given algorithm's performance. Note that this is not to be confused with a mathematical formula that has values plugged into it. Instead, it helps one analyze and compare the relative efficiency of algorithms without having to delve into detailed mathematical calculations. In short, it provides a way to express how the running time of an algorithm grows relative to the size of its input.
To get started with Big O we'll go over four main notations. I'll also include a simple real life example of each notation along with code blocks to describe my examples using JavaScript.
O(1) - Constant Time
O(1) describes an algorithm's efficiency where the amount of time it takes for the algorithm to complete is constant regardless of the input size. Therefore, it reliably performs the same way whether the input is small or large.
Imagine you had a phone book and every time you wanted to search for someone's name in the phone book, you would magically turn to the exact page of the person you were trying to find. In the code block below, the function is given an array of 1,000 different names while measuring the amount of time that it took to find the name. In the case of O(1), the algorithm isn't searching through the entire array. Instead, it's going straight to the given index. Notice that the running time came in at 0.09999999962747097 ms, the fastest of the examples.
// O(1)
const start = performance.now(); // Used to test running time
function constantTimeSearch(names, targetIndex) {
return names[targetIndex]
}
const targetIndex = names.indexOf('Thomas');
let found = constantTimeSearch(names, targetIndex);
const end = performance.now(); // Used to test running time
if (found === 'Thomas') {
console.log('FOUND!')
}
console.log(`Execution time: ${end - start} ms`);
// LOG: Execution time: 0.09999999962747097 ms
O(n) - Linear Time
O(n) describes the efficiency of an algorithm where the amount of time it takes it to complete grows linearly with the algorithm's input size. So the time that it takes to process the data is directly proportional to the size of the data.
Imagine you had the same phone book from the first example, but this time not magical. If you wanted to search for the name 'Thomas' in the phone book using O(n), you would start at page one with the A's, and flip one page at a time until you land on the page that Thomas is on. So if Thomas was on page 2500, it will take us 2500 steps to complete the task.
This process will take a long time to complete, even for a computer (relatively speaking). The code below details the example with a for loop starting from the first name and working its way one by one to Thomas. Not the most efficient with the execution time of 0.39 ms.
// O(n)
const start = performance.now(); // Used to test running time
for (let i = 0; i < names.length; i++) {
if (names[i] === 'Thomas') {
console.log('FOUND!')
}
}
const end = performance.now(); // Used to test running time
console.log(`Execution time: ${end - start} ms`);
// LOG: Execution time: 0.3999999985098839 ms
O(log n) - Logarithmic Time
Algorithms using O(log n) typically use a 'divide and conquer' strategy, which breaks down a problem into smaller sub problems in order to solve the main problem.
To make things simple, we'll use the same phone book example, but this time we'll start our search from the middle of the book while looking for Thomas. Our first step lands us in the M's section of the phone book. Since we know that 'T' in Thomas is after 'M', we can dramatically rip out everything from the phone book before section 'M'.
We now have a book that starts with section 'M' and ends in 'Z'. Our second step is to turn to the middle of the remaining book and land in section 'T'. Look at that, it took us around two steps using O(log n) to find the exact same name that we tried to find using O(n), but in a fraction of the time.
//O(log n)
const start = performance.now();
function binarySearch(names, target) {
let left = 0;
let right = names.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (names[mid] === target) {
return mid;
} else if (names[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
const targetName = "Thomas";
const index = binarySearch(names, targetName);
const end = performance.now();
if (names[index] === targetName) {
console.log('FOUND!')
}
console.log(`Execution time: ${end - start} ms`);
// LOG: Execution time: 0.10000000149011612 ms
O(n²) Quadratic Time
O(n²) describes an algorithm in which its performance time increases exponentially as the size of the input increases. These types of algorithms are extremely inefficient and generally not used in large scale processing.
With the phone book example, it would be equivalent to starting at page 0 to look for Thomas, looking at the first word and then manually comparing each letter to the letters in 'Thomas'. After completing each letter, you move on to the next name and repeat the process. In programming terms, it would be a function within a loop within a function within another loop, drastically reducing the performance of the algorithm.
function searchForMatchingNames(names, targetName) {
const matchingNames = [];
for (let i = 0; i < names.length; i++) {
const currentName = names[i];
let isMatching = true;
if (currentName.length !== targetName.length) {
isMatching = false;
} else {
for (let j = 0; j < targetName.length; j++) {
if (currentName[j] !== targetName[j]) {
isMatching = false;
break;
}
}
}
if (isMatching) {
matchingNames.push(currentName);
}
}
return matchingNames;
}
const targetName = "Thomas";
const matchingNames = searchForMatchingNames(names, targetName);
// LOG: Execution time: 11.399999998509884 ms
Conclusion
Big O notation provides insights into the efficiency of different algorithms. It doesn't give you precise timings or exact performance measurements. Instead, it focuses on how an algorithm's performance scales as the input size grows larger. It's a tool meant for analysis and decision making, especially when dealing with different algorithms and problem-solving strategies.
Sources
https://www.freecodecamp.org/news/big-o-notation-why-it-matters-and-why-it-doesnt-1674cfa8a23c/
Top comments (0)