Intro to Big O

Before I start talking about Big O it's good to know why do we need to know about it.

Let's assume that we have to different algorithms. How do we know which one is more efficient? how do we compare them? Here is where Big O comes into play.

Big O is a set of rules and terms that allows us to describe, classify, analyse, compare and discuss how efficient an algorithm is. It describes how the runtime of an algorithm grows as the input grows.

Some Big O complexities

O(1)

Constant time the runtime does grow as the input grows. If your algorithm has this complexity, probably can't do it better.

For example, this function has O(1) complexity, because the runtime its not affected as the input grows. It always do one operation if we use sum(1, 2) or sum(100000, 1000000).

function sum(n1, n2) {
  return n1 + n2
}

Operations that are considered constant:

1. Assigning variables
2. Arithmetical operations
3. Accessing element in an array by index
4. Accessing values in object by key

O(n)

Linear The runtime is bound to the input size, the runtime will grow as the input grows. Most of the times, these type of algorithms has some sort of looping mechanism(for, while, recursion).
In a loop, the complexity is the length of the loop.

function logNumbersUntil(n) {
  for (let i = 0; i < n; i++) {
    console.log(i)
  }
}