Big O. Big What ??!

If you have been reading about algorithms lately, I’m sure you encountered Big O notations. But what is it exactly?

Big O notation is the language used to describe how long an algorithm takes to run. We use it to compare the efficiency of different approaches to one problem.

Ok, and how does it work? Big O notation expresses the runtime in terms of how quickly it grows relative to the input, as the input gets arbitrarily large.

Hum… what does it mean ? It is hard to make statement about the exact runtime of an algorithm (because of external factors that might affect the time it takes a function to run), so instead we express how quickly the runtime grows. And do to so, we use the size of the input. So we can say things like, the runtime grows on the order of the size of the input O(n), or the runtime grows on the order of the square of the size of the input O(n2). Keep in mind that when calculating the runtime, the real value that is important is the calculation of the worst case scenario.

Let’s see some examples!

  • O(1)

This function runs in O(1) time (or ‘constant time) relative to its input. Here no matter how big is the array, the function will always require only one step to run.

  • O(n)

This function runs in O(n) time (or ‘linear time’), where n is the number of items in the array. If the array has 10 items, the function prints 10 times. If the array has 100 items, it will print 100 items. And so on…

  • O(n2)

This function runs in O(n2) time (or ‘quadratic time’). Here we have two nested loops, so if our array has n items our outer loop runs n times and our inner loop runs n times for each iteration of the outer loop. So we have a total of n^2 prints. If the array has 10 items, the function will print 100 times. If the array has 100 items, it will print 1,000,000 times. You can easily understand that an O(n2) runtime is not very efficient.

Now you know what Bio O is and how it works. This is only a (very) quick introduction so if you are interested in learning more about Big O notation, I recommend checking the below resources: