Basics: Big O Notation
Tags: bigo, complexities, algorithms, datastructure
Published: 2019-10-18 07:08:57

---
title: Basics: Big O Notation
published: true
description: 
tags: #big-o #complexities #algorithms #datastructure
---

This week I decided to dive into Big O notation, or algorithmic efficiency. I know it can be a bit of an intimidating topic, but the only way to get more comfortable with it is to dive in and practice! This blog post will cover the basics and serve as a refresher/guide for your journey to better understanding them. 

## What is Big O?
Big-O complexities pertain to the limiting behaviors of a function when the argument leans towards a particular value or infinity. Basically, it's used in Computer Science to illustrate the performance or complexity of an algorithm. This is always done in the worst-case scenario of that algorithm and can be applied to both the time and space required. 
![Alt Text](https://thepracticaldev.s3.amazonaws.com/i/gh1kib4sfcj83347mx7f.jpeg)

As a developer its important to be aware of the worst possible outcome of your code when it's put to the test. Being aware of this helps us developers improve our efficiency and create applications with better performance.
For instance, if you build an application and only expect a few users to visit your site then there's no problem. However, if you were, say Mark Zuckerberg and designing Facebook, then you would definitely be concerned about how your application would run as millions of users worldwide interact with your site. It is important to understand the worst-case scenario of any code that you build. As someone who is self-taught in this area I admit, it can be difficult to know what each of the complexities looks like out in the "real world" so I have prepared examples below.

Let's look at the time complexities shown in the chart above, explaining the algorithms:

## O(log n)
"O of log N"
![Alt Text](https://thepracticaldev.s3.amazonaws.com/i/60btp3m1y27rplq9i76m.png)
O(log n) is the best-case scenario. A good example of this is a binary search which divides the growth rate in two by every step of the code's execution. Therefore, on a graph, O(log n) will flatten out as the function progresses and outperform linear algorithms as the inputs increase.

## O(1)
_"O of 1"_
![Alt Text](https://thepracticaldev.s3.amazonaws.com/i/vwai9bp5evkkr8fuz7qq.png)
O(1) is referred to as __constant time__ due to the fact that despite the size of our input, it will always take the same amount of time to compute things. Constant time is regarded as the best-case scenario for a function. Basically, it's a function __without__ a loop. 

## O(n)
_"O of N"_
![Alt Text](https://thepracticaldev.s3.amazonaws.com/i/54zokqqlof1tuokpw01y.png)
O(n), also known as __linear time__ references an algorithm whose performance grows linearly, in direct correlation to the size of the input. You can think of this as one loop over a variable.

##O(n log n)
_"O of N log N"_
![Alt Text](https://thepracticaldev.s3.amazonaws.com/i/6kmn62yq0lzoifooe4np.png)
O(n log n) is referred to as __logarithmic time__. A common example of this algorithm is the implementation of a sorting function and in this case, we'll look at __Merge Sort__. Just like our O(log n)'s binary search we will divide and conquer, and break the problem into smaller sub-problems, in order to recursively solve the subproblems and then combine the solutions to the smaller problems to the initial problem. 

## O(n^2)
_"O of N squared"_
![Alt Text](https://thepracticaldev.s3.amazonaws.com/i/1o0ice3lg74dd1fiyfmb.png)
O(n^2), also known as __quadratic time__, pertains to an algorithm whose performance increases exponentially to the input data size. This is commonly seen in algorithms with nested iterations or loops and the deeper you go, the higher your exponent O(n^3), O(n^4)..etc.

## O(2^n)
_"Big O of two to the N"_
![Alt Text](https://thepracticaldev.s3.amazonaws.com/i/bnl0isp1k4zds3c6x8ig.png)
O(2^n) often referenced as __exponential time__, is an algorithm that doubles with each addition to the inputted data. The growth curve of this complexity is exponential, slow at first, and then skyrocketing. An example of this is the recursive solution for the Fibonacci sequence. 

## O(n!) 
_"O of n factorial"_

O(N!)is bad. Really, really bad. Therefore it's hardly ever shown along with the other complexities, but it's always mentioned in the chart just to show you that it still exists. 

I'll end the blog post with these useful tables from https://www.bigocheatsheet.com 

## Common Data Structure Operations
![Alt Text](https://thepracticaldev.s3.amazonaws.com/i/j7t6colddwihfy86qxsb.png)

## Array Sorting Algorithms
![Alt Text](https://thepracticaldev.s3.amazonaws.com/i/pqhhinuwq1q0y9rwwbac.png)

If you need a video explanation, Gayle Laakman McDowell, from _Cracking the Coding Interview_ does a great job in this YouTube video:

{% youtube v4cd1O4zkGw %}