Big-O Notation: Beginners Guide
Tags: computerscience, codenewbie, webdev, beginners
Published: 2018-11-12 06:26:48

In the world of programming write code as today is your last day on earth is not the main thing in the art of programming. Beyond understand what's the problem that our code will solve, we have other variables that we need to take care when we are writing code. For example:

- Complexity
- Maintainability
- Design Patterns
- Algorithms
- and beyond...

One of the most important things and the main topic of this article is the performance of our application when we are implementing an algorithm.

The performance of our algorithm helps us to make more user-friendly our application, letting the user invest only the necessary time to do the tasks and focus on other things before the go bored and close the window (browser or anything else). No matter how fast and proficient was the device from where the user is using our app. In today's world, the time is the most precious thing that we have.

Are many variables to take care when we talk about performance like the use of memory, disk space, execution time and another long beyond.
One of the most important tools to determinate the performance of our algorithm is the **Big-O Notation**.


# Big O Notation

![](https://thepracticaldev.s3.amazonaws.com/i/k9k0jpup4sol713xqh87.jpg)

The Big-O Notation is a tool that let us determinate the complexity of an algorithm, letting us take a measure of the performance of a specific algorithm. This tool measures the worst case scenario where the algorithm goes to the highest point of demand.

The main Big-O terms are these:

- O(1) ->  __Constant__
- O(n) -> __Linear__
- O(log n) -> __Logarithmic__
- O(n ^ 2) -> __Quadratic__
- O(2 ^ n) -> __Exponential__

## O(1): Constant Complexity
The __constant complexity__ is the easier, all the algorithms who, __no matter the size of the input or output, the execution time and the resources used will be always the same__, have this complexity. No matter how many times or where the algorithm is executed, __this one will have exactly the same behavior all the time__. For example:

![A function that returns the last item of an array](https://thepracticaldev.s3.amazonaws.com/i/5bdb46ohkczv50oq0r2r.png)

As we see, no matter how big is the size of the array given as an argument, the behavior will always be the same. The only thing that might change will be the output, this because the array might not have the same data stored all the time.

## O(n): Linear Complexity
We say that an algorithm has __linear complexity__ when __his execution time and/or resources used are directly proportional__ (grows up in a linear way) __to the input size__. For example:

![A function that prints each item stored in an array](https://thepracticaldev.s3.amazonaws.com/i/xaq6zgtgm1t0paetndbu.png)

To get an easier way to understand this complexity, we can compare this to an activity that we do every day (or mostly), for example, __read a book or watch a movie__. The time that we spend reading a book or watching a movie, depends on the number of pages of a book and the duration of the movie. For example, if a movie has a duration of two hours, you'll spend __two hours watching a movie__. If the book has one hundred pages and you read fifty pages in one hour, you'll spend __two hours to read all the book__.

## O(log n): Logarithmic Complexity
This complexity is present where the impact of an algorithm is __directly proportional to the logarithmic result of the input size__. In other words, when we have an input size of 10 and we need 1 second to accomplish the task with our algorithm, we need to do exactly the same task with an input size of 100 in 2 seconds, with an input size of 1000 in 3 seconds and so on.

![Binary search (thanks to room_js)](https://thepracticaldev.s3.amazonaws.com/i/uzbixq65z45o2gqbxzso.png)

One interesting example is the [binary search](https://en.wikipedia.org/wiki/Binary_search_algorithm). In this algorithm, we divide the array (previously ordered) into two parts. We take the middle index as a reference to get the value at the middle of the array. If the number in that spot is equal to the number we are looking for, we return the middle index adding up the prefix that we use to find the spot where the number we are looking for is stored. Thanks to that, if the number is bigger than the number stored at the middle of the array, we look for the number in the right side of the array, instead, if is lower, we look in the left side of the array. After that, we use the prefix to use as the new prefix in the next iteration as a recursive way. We repeat this loop until get the given number.

## O( n^2 ): Quadratic Complexity
The __quadratic complexity__ is present when the impact of the algorithm is __directly proportional to the square of the input size__. This means, if we have an array as input with a length of 4 spots and we want to compare to look if the array has repeated items, we need to do 16 comparations to accomplish our task. This complexity is common in sorting algorithms like [bubble sort](https://www.geeksforgeeks.org/bubble-sort/), [insertion sort](https://en.wikipedia.org/wiki/Insertion_sort), and the [selection sort](https://en.wikipedia.org/wiki/Selection_sort).

![A function that prints "miau" when two items are equal in an array](https://thepracticaldev.s3.amazonaws.com/i/8lx1q2uyh5s21gb1vjya.png)

In this function, the complexity can grow up if we add more for loops. __This could make us go to an O(n * n) complexity__.

## O( 2^n ): Exponential Complexity
When an algorithm has __exponential complexity__, this means that __the complexity will double with each additional item in the input__. If 10 items take 100 seconds, 11 would take 200 seconds, 13 would take 400 seconds and so on.


![Fibonacci sequence](https://thepracticaldev.s3.amazonaws.com/i/igf2xwae7v3bdj1ixp17.png)

This doesn't mean that only exists O( 2^n ), this is just for explanation purpose. Can grow to O( 3^n ), O( 4^n ) and so on.

# Wrapping Up
I hope this helps you to understand more the Big-O Notation, it's a great help to measure the complexity of an algorithm, exists many more tools to do this but this is one of the more common.

If you have questions or want to correct some mistakes, feel free to leave your comment below. I'm leaving below a little list of resources about Big-O Notation.

# More resources
- https://es.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-o-notation

- https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

- https://en.wikipedia.org/wiki/Big_O_notation

- http://interactivepython.org/runestone/static/pythonds/AlgorithmAnalysis/BigONotation.html