Big O notation

Big O notation is used to describe the time spent by an algorithm to run.

\(O(1)\) - Constant time

const x = 10
printf("Lorem ipsum")

\(O(log(n))\) - Log time

for(int i = 1; i <= n; i = i * 2)
  print "hello";

Notice the post operation of the for loop multiples the current value of i by 2, so i goes from 1 to 2 to 4 to 8 to 16 to 32…

for(double i = 1; i < n; i = i * 1.02)
  print "hello";

As long as the number is greater than 1 and the result is repeatedly multiplied against itself (i = i * 1.02), that you are looking at a logarithmic algorithm.

\(O(n)\) Linear time

for(int i = 0; i < n; i++)
  print "hello";

\(O(n*log(n))\) nlog(n)

Think of this as a combination of O(log(n)) and O(n). The nesting of the for loops help us obtain the O(n*log(n))

for(int i = 0; i < n; i++)
  for(int j = 1; j < n; j = j * 2)
    print "hello";

\(O(n^2)\) - n squared

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j++)
    print "hello";

Is obtained easily by nesting standard for loops.

\(O(2^n)\) - exponential time example

When the algorithm specifies a growth rate that doubles every time the input data set is added.

const recursiveFibonacci = (n) => {
  if (n < 2) {
    return n;
  }
  return recursiveFibonacci(n - 1) + recursiveFibonacci(n - 2);
};

console.log(recursiveFibonacci(6)); // 8

\(O(n!)\) - factorial time

For example, the factorial of 5, or 5!, is:

5 * 4 * 3 * 2 * 1 = 120

We will find ourselves writing algorithms with factorial time complexity when calculating permutations and combinations.

Those are basically NP problems (Nondeterministic Polynomial).