Intro to Big O Notation

Have you just wrapped up a bootcamp? How about a course/book/YouTube video on data structures and algorithms? Chances are that you have come across something called Big O Notation and time/space complexity (nope, sorry not the kind that creates wormholes).

Big O Complexity Chart
Image from https://www.bigocheatsheet.com/

Big O notation is a way of describing how the time or memory needed to execute an algorithm grows with respect to the number of inputs. I’ll go over some of the more common ones (constant time, linear time, and quadratic time) in this blog.

An algorithm with O(1) time will return in the same amount of time regardless of the size of the input. This has the least complexity and is the fastest Big O time. A common example of O(1) time is accessing an array value with an array index. In this example, we have 5 array elements, but it would take the same amount of time to run if we had 5000 array elements.

const myArray = [1,2,3,4,5];
myArray[3] // => 4

An algorithm with O(n) time (pronounced “O of n”, “Order n”, or “big O of n”) means that its speed is determined by the number of inputs (n). This might not be a problem if there were only 5 elements, but if there were 5000, this would be bad news and our algorithm would run very slowly! An example of O(n) time would be this:

function linearTime(array) {
for (let i = 0; i < array.length; i++) {
if (array[i] === "monstera") {
return array[i]
}
}
}
const plantArray = ['ficus', 'sansevieria', 'monstera', 'scindapsus'];
linearTime(plantArray)

Using our given plantArray , we find ‘monstera’ pretty quickly, but if we had a much bigger plant array with 2000 elements in it and ‘monstera’ was towards the end of the array? It would take much longer!

An algorithm with O(n²) time (pronounced “O of n squared”, “Order n squared”, or “big O of n squared”) is the slowest time that I have included in this article. If the number of input elements (n) doubles, then the time it will take to run nearly quadruples! An example of quadratic time is a nested loop. We’ll use the classic two sum problem to demonstrate this:

// Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
function twoSum(nums, target) { let indices = [];
for(let i = 0; i < nums.length; i++) { for(let j = i + 1; j < nums.length; j++) { if(nums[i] + nums[j] === target) { indices.push(i, j); } } } return indices;};

Thanks for reading and I hope you enjoyed this crash course into Big O notation!