loading...
Cover image for Starter Guide to Big O Notation

Starter Guide to Big O Notation

proiacm profile image CiaraMaria ・3 min read

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().

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 ) we simplify to O()

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)
  }
}
Enter fullscreen mode Exit fullscreen mode

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)
  }
}
Enter fullscreen mode Exit fullscreen mode

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()

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(), 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);
    }
  }
}
Enter fullscreen mode Exit fullscreen mode

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().

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!

Discussion

pic
Editor guide
Collapse
thinkverse profile image
Kim Hallberg

Saw this on Dev's daily.dev feed as a featured post. At first, I was a bit apprehensive. Whenever I've read posts on Big 0 - even if they were for beginners. They've mostly used complex and contrived examples that make me feel dumb. So I've had a hard time wrapping my brain around the concept.

Glad to say this was not that. Thank you for not making me feel like I'm a child and for giving me a better understanding of the basics. 😀

Collapse
proiacm profile image
CiaraMaria Author

I'm so glad to hear that, Kim! Thank you so much for this. I've been confused by posts on Big O as well, so I'm happy to hear that I was able to break it down clearly.

Collapse
deta19 profile image
mihai

nice one, thank you!!

Collapse
proiacm profile image
CiaraMaria Author

You're welcome! :]

Collapse
wagslane profile image
Lane Wagner

Thanks for the post :) I recently published a more in depth course on this topic for anyone who really wants to dive into Big O: qvault.io/big-o-algorithms-course