Starter Guide to Big O Notation

As a developer without a Computer Science background, Big O Notation is one of those concepts that I've had to double down on in order to improve my algorithmic skills. In this post, I will cover some basics of Big O using JavaScript.

What is Big O Notation?

Big O Notation is used to describe how long a function takes to run and allows us to talk formally about how the runtime grows as the inputs grow. It specifically describes the worst-case scenario in terms of runtime.

Big O is expressed as O(n) where n is the size of the input.
We will look at three specific expressions: O(1), O(n), and O(n²).

When determining the amount of time it takes to run an algorithm, we have some helpful rules of thumb:

1. When considering Big O, we only care about the broadest view. We're looking at what happens as n gets ridiculously large. As this happens, the significant effect of adding 100 or multiplying by 5 decreases.

2. Constants don't matter:

• If we have O(5 n) we simplify to O(n)
• If we have O(42) we simplify to O(1)
• If we have O(10 n²) we simplify to O(n²)

O(1)

This expression means that a function takes a constant amount of runtime. Whether the input is 1 or 1000, as the input grows the time expended remains the same.

For example:

function logAtMostFive(n) {
  for (let i = 1; i <= Math.min(5, n); i++) {
    console.log(i)
  }
}

In the above function, regardless of what n is the runtime will remain constant. So, if you run this function you'll notice that whether you pass in 5 or 200, the log will only be 1, 2, 3, 4, 5.

As a result, we can say that the Big O Notation for this function is O(1).

O(n)

This expression means that it takes an amount of time linear with the size of n. The runtime will increase in relation to the increase of the input.

For example:

function logAtLeastFive(n) {
  for (let i = 1; i <= Math.max(5, n); i++) {
    console.log(i)
  }
}

In the above function, we see the opposite effect as in the previous example. As n increases, runtime increases in relation to n. If you run this function, you'll notice that if you pass in 5 the log will be 1, 2, 3, 4, 5 however, if you pass in 200 the log will be 1, 2, 3, 4, 5, 6, 7...200

As a result, we can say that the Big O Notation for this function is O(n).

O(n²)

This expression means that an algorithm's runtime is directly proportional to the square of n. Time will exponentially increase in relation to the increase of the input. This is common in functions that involve nested iterations. Deeper nesting will result in O(n³), O(n⁴), etc.

For example:

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

In the above function, as n increases, the runtime increases exponentially. This can seriously inhibit performance as the size of n gets ridiculously large as mentioned earlier.

As a result, we can say that the Big O Notation for this function is O(n²).

Conclusion

Big O Notation allows us to describe the amount of time an algorithm will take to run. As applications grow and the amount or size of data being handled grows, the way our functions process that information becomes critical.

Hopefully, you enjoyed this starter guide to Big O!