Big O
Published on 02/07/2019
1 min read
In category
JavaScript
Big O Notation
Allows us to express how the runtime of an algorithm grows as the inputs grow.
O(1)
function addUpTo(n) {
return n * (n + 1) / 2;
}
addUpToN()
performs three operations each time it is called.
1 addition, 1 multiplication, and 1 division.
However, the number of operations does NOT increase with the size of the argument. In general the complexity is O(1)
O(n)
function addUpTo(n) {
let total = 0;
for (let i = 0; i <= n ; i++) {
total += i;
}
return total
}
In contrast, the second version is much less efficient. The number of operations grows as n grows. In the for loop, we compare i to n, n times, total += i, n times, i++ n times. It adds up. I general, we say the complexity is O(N).
O(n^2)
function nestedForLoop(n) {
for (var i=0; i < n; i++) {
for (var j=0; j < n; j++) {
console.log(i, j);
}
}
}
Here, we have an O(n) operation inside of an O(n) operation, which results in an O(n^2) complexity.
Some shortcuts

Arithmetic operations are constant.

Variable assignment is constant.

Accessing elements in an array is constant.

in a loop, the complexity is the length of the loop times the complexity of what happens inside the loop.