Big O

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

  1. Arithmetic operations are constant.

  2. Variable assignment is constant.

  3. Accessing elements in an array is constant.

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

Big O Chart

my_button

arrow_back

Previous

React Use Effect

Next

CSS Grid Notes
arrow_forward