Big O Notation Cool Examples

Example 1


function printFirstItem(items) {
console.log(items[0]);
}


This function runs in O(1)O(1) time (or "constant time") relative to its input. The input array could be 1 item or 1,000 items, but this function would still just require one "step."

Example 2

function printAllItems(items) {
items.forEach(item => {
console.log(item);
});
}

This function runs in O(n)O(n) time (or "linear time"), where nn is the number of items in the array. If the array has 10 items, we have to print 10 times. If it has 1,000 items, we have to print 1,000 times.

Example 3

function printAllPossibleOrderedPairs(items) {
items.forEach(firstItem => {
items.forEach(secondItem => {
console.log(firstItem, secondItem);
});
});
}

Here we're nesting two loops. If our array has nn items, our outer loop runs nn times and our inner loop runs nn times for each iteration of the outer loop, giving us n^2
total prints.

Some rules

N could be the actual input, or the size of the input

function sayHiNTimes(n) {
for (let i = 0; i < n; i++) {
console.log('hi');
}
}
function printAllItems(items) {
items.forEach(item => {
console.log(item);
});
}

Drop the constants

When you're calculating the big O complexity of something, you just throw out the constants.

`function printAllItemsTwice(items) {
items.forEach(item => {
console.log(item);
});

// Once more, with feeling
items.forEach(item => {
console.log(item);
});
}
This is O(2n)O(2n), which we just call O(n)O(n).`

Drop the less significant terms

`function printAllNumbersThenAllPairSums(numbers) {

console.log('these are the numbers:');
numbers.forEach(number => {
console.log(number);
});

console.log('and these are their sums:');
numbers.forEach(firstNumber => {
numbers.forEach(secondNumber => {
console.log(firstNumber + secondNumber);
});
});
}`

Here our runtime is O(n + n^2)O(n+n2), which we just call O(n^2)O(n2). Even if it was O(n^2/2 + 100n)O(n2/2+100n), it would still be O(n^2)O(n2).

Thanks for reading <3