It’s very important while building a new feature/functionality to get the job done but what’s more important is how effecient is, and the judge in this case is the Big O Notation.
Big O Notation is a way used by developers to measure the efficiency of an algorithm, It describes the worst-case scenario, allowing developers to understand the potential risk in their code.
O(1) – Constant Time:
The execution time is constant and does not change with the input size.
/**Accessing an element in an array by index takes
the same amount of time regardless of the array's size**/.
function getFirstElement(array) {
return array[0];
}
JavaScriptO(n) – Linear Time:
The execution time grows linearly with the input size.
/**Accessing an element in an array by index takes
the same amount of time regardless of the array's size**/
function getFirstElement(array) {
return array[0];
}
JavaScriptO(n^2) – Quadratic Time:
The execution time grows quadratically with the input size, common in nested loops.
/**The nested loops lead to a time complexity of O(n^2)
since for each element, we might have to compare it with every other element.**/
function bubbleSort(array) {
for (let i = 0; i < array.length; i++) {
for (let j = 0; j < array.length - i - 1; j++) {
if (array[j] > array[j + 1]) {
// Swap
[array[j], array[j + 1]] = [array[j + 1], array[j]];
}
}
}
return array;
}
JavaScriptO(n log n) – Linearithmic Time:
Common in efficient sorting algorithms like merge sort.
/** The merge sort divides the array into halves recursively (log n)
and then merges the sorted halves (n), resulting in O(n log n) complexity.**/
function mergeSort(array) {
if (array.length <= 1) return array;
const mid = Math.floor(array.length / 2);
const left = mergeSort(array.slice(0, mid));
const right = mergeSort(array.slice(mid));
return merge(left, right);
}
function merge(left, right) {
let result = [];
while (left.length && right.length) {
if (left[0] < right[0]) result.push(left.shift());
else result.push(right.shift());
}
return result.concat(left, right);
}
JavaScriptNow to make test your knowledge with measuring Big O Notation, try to guess the Big O Notation for the following code snippets:
function getFirstElement(arr) {
return arr[0];
}
JavaScriptAnswer…
The Big O notation for this code is O(1).
Explanation:
The function getFirstElement
returns the first element of an array. This operation takes constant time because it doesn’t depend on the size of the array—it simply accesses the first element, making the time complexity O(1).
function findMax(arr) {
let max = arr[0];
for (let i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
JavaScriptAnswer…
The Big O notation for this code is O(n).
Explanation:
The function findMax
iterates through each element of the array to find the maximum value. As the number of elements (n) increases, the number of operations grows linearly with it, resulting in a time complexity of O(n).
function printPairs(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length; j++) {
console.log(arr[i], arr[j]);
}
}
}
JavaScriptAnswer…
The Big O notation for this code is O(n^2).
Explanation:
The function printPairs
has two nested loops, each running n
times where n
is the length of the array. This results in the total number of operations being proportional to n * n, giving a time complexity of O(n^2).
Your writing has a way of making even the most complex topics accessible and engaging. I’m constantly impressed by your ability to distill complicated concepts into easy-to-understand language.