Starter Guide to Big O Notation

Starter Guide to Big O Notation:

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 nincreases, 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!

from Tumblr https://generouspiratequeen.tumblr.com/post/635562637093224448

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s