Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
1 contributor

Users who have contributed to this file

302 lines (220 sloc) 12.2 KB

Big O examples

There are many kinds of algorithms. Most of them fall into one of the eight time complexities that we are going to explore in this chapter.

Eight Running Time complexity You Should Know
  • Constant time: O(1)

  • Logarithmic time: O(log n)

  • Linear time: O(n)

  • Linearithmic time: O(n log n)

  • Quadratic time: O(n2)

  • Cubic time: O(n3)

  • Exponential time: O(2n)

  • Factorial time: O(n!)

We a going to provide examples for each one of them.

Before we dive in, here’s a plot with all of them.

CPU time needed vs. Algorithm runtime as the input size increases
Figure 1. CPU operations vs. Algorithm runtime as the input size grows

The above chart shows how the running time of an algorithm is related to the amount of work the CPU has to perform. As you can see O(1) and O(log n) are very scalable. However, O(n2) and worst can make your computer run for years 😵 on large datasets. We are going to give some examples so you can identify each one.

Constant

Represented as O(1), it means that regardless of the input size the number of operations executed is always the same. Let’s see an example.

Finding if an array is empty

Let’s implement a function that finds out if an array is empty or not.

link:../../../src/runtimes/01-is-empty.js[]

Another more real life example is adding an element to the begining of a part02-linear-data-structures.asc. You can check out the implementation here.

As you can see, in both examples (array and linked list) if the input is a collection of 10 elements or 10M it would take the same amount of time to execute. You can’t get any more performant than this!

Logarithmic

Represented in Big O notation as O(log n), when an algorithm has this running time it means that as the size of the input grows the number of operations grows very slowly. Logarithmic algorithms are very scalable. One example is the binary search.

Searching on a sorted array

The binary search only works for sorted lists. It starts searching for an element on the middle of the array and then it moves to the right or left depending if the value you are looking for is bigger or smaller.

link:../../../src/runtimes/02-binary-search.js[]

This binary search implementation is a recursive algorithm, which means that the function binarySearch calls itself multiple times until the solution is found. The binary search splits the array in half every time.

Finding the runtime of recursive algorithms is not very obvious sometimes. It requires some tools like recursion trees or the Master Theorem. The binarySearch divides the input in half each time. As a rule of thumb, when you have an algorithm that divides the data in half on each call you are most likely in front of a logarithmic runtime: O(log n).

Linear

Linear algorithms are one of the most common runtimes. It’s represented as O(n). Usually, an algorithm has a linear running time when it iterates over all the elements in the input.

Finding duplicates in an array using a map

Let’s say that we want to find duplicate elements in an array. What’s the first implementation that comes to mind? Check out this implementation:

link:../../../src/runtimes/03-has-duplicates.js[]
hasDuplicates has multiple scenarios:
  • Best-case scenario: first two elements are duplicates. It only has to visit two elements.

  • Worst-case scenario: no duplicated or duplicated are the last two. In either case, it has to visit every item on the array.

  • Average-case scenario: duplicates are somewhere in the middle of the collection. Only, half of the array will be visited.

As we learned before, the big O cares about the worst-case scenario, where we would have to visit every element on the array. So, we have an O(n) runtime.

Space complexity is also O(n) since we are using an auxiliary data structure. We have a map that in the worst case (no duplicates) it will hold every word.

Linearithmic

An algorithm with a linearithmic runtime is represented as O(n log n). This one is important because it is the best runtime for sorting! Let’s see the merge-sort.

Sorting elements in an array

The Merge Sort, like its name indicates, has two functions merge and sort. Let’s start with the sort function:

Sort part of the mergeSort
link:../../../src/algorithms/sorting/merge-sort.js[]
  1. If the array only has two elements we can sort them manually.

  2. We divide the array into two halves.

  3. Merge the two parts recursively with the merge function explained below

Merge part of the mergeSort
link:../../../src/algorithms/sorting/merge-sort.js[]

The merge function combines two sorted arrays in ascending order. Let’s say that we want to sort the array [9, 2, 5, 1, 7, 6]. In the following illustration, you can see what each function does.

Mergesort visualization
Figure 2. Mergesort visualization. Shows the split, sort and merge steps

How do we obtain the running time of the merge sort algorithm? The mergesort divides the array in half each time in the split phase, log n, and the merge function join each splits, n. The total work is O(n log n). There are more formal ways to reach this runtime, like using the Master Method and recursion trees.

Quadratic

Running times that are quadratic, O(n2), are the ones to watch out for. They usually don’t scale well when they have a large amount of data to process.

Usually they have double-nested loops, where each one visits all or most elements in the input. One example of this is a naïve implementation to find duplicate words on an array.

Finding duplicates in an array (naïve approach)

If you remember we have solved this problem more efficiently on the Linear section. We solved this problem before using an O(n), let’s solve it this time with an O(n2):

Naïve implementation of has duplicates function
link:../../../src/runtimes/05-has-duplicates-naive.js[]

As you can see, we have two nested loops causing the running time to be quadratic. How much difference is there between a linear vs. quadratic algorithm?

Let’s say you want to find a duplicated middle name in a phone directory book of a city of ~1 million people. If you use this quadratic solution you would have to wait for ~12 days to get an answer 🐢; while if you use the linear solution you will get the answer in seconds! 🚀

Cubic

Cubic O(n3) and higher polynomial functions usually involve many nested loops. An example of a cubic algorithm is a multi-variable equation solver (using brute force):

Solving a multi-variable equation

Let’s say we want to find the solution for this multi-variable equation:

3x + 9y + 8z = 79

A naïve approach to solve this will be the following program:

Naïve implementation of multi-variable equation solver
link:../../../src/runtimes/06-multi-variable-equation-solver.js[]
Warning
This is just an example, there are better ways to solve multi-variable equations.

As you can see three nested loops usually translates to O(n3). If you have a four variable equation and four nested loops it would be O(n4) and so on when we have a runtime in the form of O(nc), where c > 1, we refer to this as a polynomial runtime.

Exponential

Exponential runtimes, O(2n), means that every time the input grows by one the number of operations doubles. Exponential programs are only usable for a tiny number of elements (<100) otherwise it might not finish in your lifetime. 💀

Let’s do an example.

Finding subsets of a set

Finding all distinct subsets of a given set can be implemented as follows:

Subsets in a Set
link:../../../src/runtimes/07-sub-sets.js[]
  1. Base case is empty element.

  2. For each element from the input append it to the results array.

  3. The new results array will be what it was before + the duplicated with the appended element.

Every time the input grows by one the resulting array doubles. That’s why it has an O(2n).

Factorial

Factorial runtime, O(n!), is not scalable at all. Even with input sizes of ~10 elements, it will take a couple of seconds to compute. It’s that slow! 🍯🐝

Factorial

A factorial is the multiplication of all the numbers less than itself down to 1.

For instance:
  • 3! = 3 x 2 x 1 = 6

  • 5! = 5 x 4 x 3 x 2 x 1 = 120

  • 10! = 3,628,800

  • 11! = 39,916,800

Getting all permutations of a word

One classic example of an O(n!) algorithm is finding all the different words that can be formed with a given set of letters.

Word’s permutations
link:../../../src/runtimes/08-permutations.js[]

As you can see in the getPermutations function, the resulting array is the factorial of the word length.

Factorial starts very slow, and quickly becomes uncontrollable. A word size of just 11 characters would take a couple of hours in most computers! 🤯

Summary

We went through 8 of the most common time complexities and provided examples for each of them. Hopefully, this will give you a toolbox to analyze algorithms.

Table 1. Most common algorithmic running times and their examples
Big O Notation Name Example(s)

O(1)

part01-algorithms-analysis.asc

part01-algorithms-analysis.asc

O(log n)

part01-algorithms-analysis.asc

part01-algorithms-analysis.asc

O(n)

part01-algorithms-analysis.asc

part01-algorithms-analysis.asc

O(n log n)

part01-algorithms-analysis.asc

part01-algorithms-analysis.asc

O(n2)

part01-algorithms-analysis.asc

part01-algorithms-analysis.asc

O(n3)

part01-algorithms-analysis.asc

part01-algorithms-analysis.asc

O(2n)

part01-algorithms-analysis.asc

part01-algorithms-analysis.asc

O(n!)

part01-algorithms-analysis.asc

part01-algorithms-analysis.asc

You can’t perform that action at this time.