Big O, loop runtimes

Big O is usually introduced using for loops with loops. For example:

for(var i = 0; i <= n; i++) {
  console.log(n);
}

Has a Big O of O(n), because its growth is dependent on the value of n.

We can also have more than one loop. For example:

for(var i = 0; i <= n; i++) {
  console.log(n);
}

for(var j = 0; j <= n; j++) {
  console.log(n);
}

Which is O(2n) which is pretty much just O(n)

for(var i = 0; i <= n; i++) {
  console.log(n);
}

for(var j = 0; j <= m; j++) {
  console.log(m);
}

Which is O(n+m)

Lets look at a nested loop

for(var i = 0; i <= n; i++) {
  for(var j = 0; j <= n; j++) {
    console.log(n);
  }
}

This loop has n iterations and the loop inside it also has n iterations.

So we multiply n by n instead of adding them together like we would with two loops that are adjacent to each other to get O(n^2)

Note that for both loops we’re iterating based off a our variable n.

But what if our loops is dependent on the value m?

for(var i = 0; i <= n; i++) {
  for(var j = 0; j <= m; j++) {
    console.log(n + ' ' + m);
  }
}

Then we woud have a runtime of O(n*m)

What if we get through the loop at a faster rate than we would normally expect, such as

for(var i = 0; i*i <= n; i++) {
}

This would means we would have a runtime of O(n^1/2), otherwise known as O(sqrt(n))

We could also have a cubed root runtime such as

for(var i = 0; i*i*i <= n; i++) {
}