Big O Notation Explained

# Big O Notation Explained

You've probably come across Big O while programming or reading about programming at some point. You might've googled it at that point and understood it for a while, but if you're like me, you probably forgot about it because you didn't understand it fully. Well, not to worry, I will explain it here.

It basically describes how well an algorithm performs, as the inputs grow. As we add more inputs to an algorithm, the complexity grows. Two things grow as the number of inputs grows. If it takes the algorithm more time, that means that the time complexity is bigger, meaning it takes more time to run the algorithm. Or, if it required more memory, we call it space complexity.

`O(n)`

It is denoted with a capital O, and the (n) is the number of inputs. For example:

``````function addUpTo(n) {
return n * (n+1) / 2
``````

This is just a simple function, that takes in the input n, and adds numbers up to it. We can say that this function has O(1). After a big O, anything you see in parentheses describes the changes in the complexity of the function. So here, as we have 1, as the input of the function grows, it has no change on the complexity.

Now, if we have O(n), that means that the run time increases at the same pace as the input. This is more noticeable with more complex functions. For example:

``````const array = [1,2,3,4,5,6]

function printArrayValues(n) {
for(let i = 0; i < n.length; i++) {
console.log(n[i])
}
}
``````

Here we have an array and the function that just prints the values of the array. We say that we have O(n) since the more values we have in the array, the longer it will run. Usually, when you see a loop, it means that the function or algorithm has an O(n).

There are two other big O notations, that I won't go into too much detail about in this article.

O(n²) is quadratic time. Meaning the runtime is the squared size of the input data.

O(log n) is logarithmic time. This means that the run time increases in proportion to the logarithm of the input size, which in turn means that the run time barely increases as you exponentially increase the input.

If you'd like to know more about the Big O Notation or reference, there is the Big-O Cheat Sheet, which is a great site for understanding Big O better.