Exploring Time Complexity.
Published: 2021-10-03 10:14:03

# Exploring Time Complexity In JavaScript {.p-name}

What is time complexity?

---

### Exploring Time Complexity In JavaScript {#2f17 .graf .graf--h3 .graf--leading .graf--title name="2f17"}

\

\

![](https://cdn-images-1.medium.com/max/800/0*KP9Vgq0F-GHrNsbE.gif)

### What is time complexity? {#1556 .graf .graf--h3 .graf-after--figure name="1556"}

\

To recap time complexity estimates how an algorithm performs regardless
of the kind of machine it runs on. You can get the time complexity by
“counting” the number of operations performed by your code. This time
complexity is defined as a function of the input size `n`{.markup--code
.markup--p-code} using Big-O notation. `n`{.markup--code
.markup--p-code} indicates the input size, while O is the worst-case
scenario growth rate function.

We use the Big-O notation to classify algorithms based on their running
time or space (memory used) as the input grows. The `O`{.markup--code
.markup--p-code} function is the growth rate in function of the input
size `n`{.markup--code .markup--p-code}.

Here are the big O cheatsheet and examples that we will cover in this
post before we dive in. Click on them to go to the implementation.

![](https://cdn-images-1.medium.com/max/800/1*OH7UGBalhUnQ0jIB28JHvQ.png)

\

---

\

---

### O(1) — Constant time {#136f .graf .graf--h3 .graf--leading name="136f"}

`O(1)`{.markup--code .markup--p-code} describes algorithms that take the
same amount of time to compute regardless of the input size.

For instance, if a function takes the same time to process ten elements
and 1 million items, then we say that it has a constant growth rate or
`O(1)`{.markup--code .markup--p-code}. Let’s see some cases.

Examples of constant runtime algorithms:

- Find if a number is even or odd.
- Check if an item on an array is null.
- Print the first element from a list.
- Find a value on a map.

### Odd or Even {#852b .graf .graf--h3 .graf-after--li name="852b"}

Find if a number is odd or even.

```{#3634 .graf .graf--pre .graf-after--p name="3634"}
function isEvenOrOdd(n) {  return n % 2 ? 'Odd' : 'Even';}
```

```{#4ee2 .graf .graf--pre .graf-after--pre name="4ee2"}
console.log(isEvenOrOdd(10)); // => Evenconsole.log(isEvenOrOdd(10001)); // => Odd
```

\

> _Do not be fooled by one-liners. They don’t always translate to
> constant times. You have to be aware of how they are implemented._

If you have a method like `Array.sort()`{.markup--code .markup--p-code}
or any other array or object method, you have to look into the
under-the-hood implementation to determine its running time.

Primitive operations like sum, multiplication, subtraction, division,
modulo, bit shift, etc., have a constant runtime. Did you expect that?
Let’s go into detail about why they are constant time. If you use the
schoolbook long multiplication algorithm, it would take
`O(n2)`{.markup--code .markup--p-code} to multiply two numbers. However,
most programming languages limit numbers to max value (e.g. in JS:
`Number.MAX_VALUE`{.markup--code .markup--p-code} is
`1.7976931348623157e+308`{.markup--code .markup--p-code}). So, you
cannot operate numbers that yield a result greater than the
`MAX_VALUE`{.markup--code .markup--p-code}. So, primitive operations are
bound to be completed on a fixed amount of instructions
`O(1)`{.markup--code .markup--p-code} or throw overflow errors (in JS,
`Infinity`{.markup--code .markup--p-code} keyword).

This example was easy. Let’s do another one.

### Look-up table {#6cc9 .graf .graf--h3 .graf-after--p name="6cc9"}

Given a string, find its word frequency data.

```{#1a00 .graf .graf--pre .graf-after--p name="1a00"}
const dictionary = {the: 22038615, be: 12545825, and: 10741073, of: 10343885, a: 10144200, in: 6996437, to: 6332195 /* ... */};
```

```{#4fe6 .graf .graf--pre .graf-after--pre name="4fe6"}
function getWordFrequency(dictionary, word) {return dictionary[word];}
```

```{#f24c .graf .graf--pre .graf-after--pre name="f24c"}
console.log(getWordFrequency(dictionary, 'the'));console.log(getWordFrequency(dictionary, 'in'));
```

Again, we can be sure that even if the dictionary has 10 or 1 million
words, it would still execute line 4 once to find the word. However, if
we decided to store the dictionary as an array rather than a hash map,
it would be a different story. In the next section, we will explore
what’s the running time to find an item in an array.

> *Only a hash table with a perfect*hash function*will have a worst-case
> runtime of*O(1)*. The ideal hash function is not practical, so some
> collisions and workarounds lead to a worst-case runtime of*O(n)*.
> Still, on*average*, the lookup time is*O(1)_._

### O(n) — Linear time {#c5cc .graf .graf--h3 .graf-after--blockquote name="c5cc"}

Linear running time algorithms are widespread. These algorithms imply
that the program visits every element from the input.

Linear time complexity `O(n)`{.markup--code .markup--p-code} means that
the algorithms take proportionally longer to complete as the input
grows.

Examples of linear time algorithms:

- Get the max/min value in an array.
- Find a given element in a collection.
- Print all the values in a list.

### The largest item on an unsorted array {#8ddd .graf .graf--h3 .graf-after--li name="8ddd"}

Let’s say you want to find the maximum value from an unsorted array.

```{#a35d .graf .graf--pre .graf-after--p name="a35d"}
function findMax(n) {  let max;  let counter = 0;
```

```{#766d .graf .graf--pre .graf-after--pre name="766d"}
for (let i = 0; i < n.length; i++) {counter++;if(max === undefined || max < n[i]) {max = n[i];}}
```

```{#4f56 .graf .graf--pre .graf-after--pre name="4f56"}
console.log(n: ${n.length}, counter: ${counter});return max;}
```

How many operations will the `findMax`{.markup--code .markup--p-code}
function do?

Well, it checks every element from `n`{.markup--code .markup--p-code}.
If the current item is more significant than `max`{.markup--code
.markup--p-code} it will do an assignment.

Notice that we added a counter to count how many times the inner block
is executed.

If you get the time complexity, it would be something like this:

- Line 2–3: 2 operations
- Line 4: a loop of size n
- Line 6–8: 3 operations inside the for-loop.

So, this gets us `3(n) + 2`{.markup--code .markup--p-code}.

Applying the Big O notation that we learn in the [previous
post](https://master--bgoonz-blog.netlify.app/blog/2018/04/04/how-you-can-change-the-world-learning-data-structures-algorithms-free-online-course-tutorial/#Asymptotic-analysis),
we only need the biggest order term, thus `O(n)`{.markup--code
.markup--p-code}.

We can verify this using our `counter`{.markup--code .markup--p-code}.
If `n`{.markup--code .markup--p-code} has 3 elements:

```{#d42f .graf .graf--pre .graf-after--p name="d42f"}
findMax([3, 1, 2]);// n: 3, counter: 3
```

or if `n`{.markup--code .markup--p-code} has 9 elements:

```{#8006 .graf .graf--pre .graf-after--p name="8006"}
findMax([4,5,6,1,9,2,8,3,7])// n: 9, counter: 9
```

Now imagine that you have an array of one million items. Do you think it
will take the same time? Of course not. It will take longer to the size
of the input. If we plot `n`{.markup--code .markup--p-code} and
`findMax`{.markup--code .markup--p-code} running time, we will have a
linear function graph.

![](https://cdn-images-1.medium.com/max/800/0*kFuxx3O5jSwHx5Mo.jpg)

### O(n²) — Quadratic time {#e052 .graf .graf--h3 .graf-after--figure name="e052"}

A function with a quadratic time complexity has a growth rate of n2. If
the input is size 2, it will do four operations. If the input is size 8,
it will take 64, and so on.

Here are some examples of quadratic algorithms:

- Check if a collection has duplicated values.
- Sorting items in a collection using bubble sort, insertion sort, or
  selection sort.
- Find all possible ordered pairs in an array.

Let’s implement the first two.

### Has duplicates {#bdc1 .graf .graf--h3 .graf-after--p name="bdc1"}

You want to find duplicate words in an array. A naïve solution will be
the following:

```{#1d31 .graf .graf--pre .graf-after--p name="1d31"}
function hasDuplicates(n) {  const duplicates = [];  let counter = 0; // debug
```

```{#fd83 .graf .graf--pre .graf-after--pre name="fd83"}
for (let outter = 0; outter < n.length; outter++) {for (let inner = 0; inner < n.length; inner++) {counter++; // debug
```

```{#8c3d .graf .graf--pre .graf--empty .graf-after--pre name="8c3d"}

```

```{#8398 .graf .graf--pre .graf--empty .graf-after--pre name="8398"}

```

```{#a2ce .graf .graf--pre .graf-after--pre name="a2ce"}
if(outter === inner) continue;
```

```{#d302 .graf .graf--pre .graf-after--pre name="d302"}
  if(n[outter] === n[inner]) {    return true;  }}}
```

```{#0034 .graf .graf--pre .graf-after--pre name="0034"}
console.log(n: ${n.length}, counter: ${counter}); // debugreturn false;}
```

Time complexity analysis:

- Line 2–3: 2 operations
- Line 5–6: double-loop of size n, so `n^2`{.markup--code
  .markup--li-code}.
- Line 7–13: has \~3 operations inside the double-loop

We get `3n^2 + 2`{.markup--code .markup--p-code}.

When we have an asymptotic analysis, we drop all constants and leave the
most critical term: `n^2`{.markup--code .markup--p-code}. So, in the big
O notation, it would be `O(n^2)`{.markup--code .markup--p-code}.

We are using a counter variable to help us verify. The
`hasDuplicates`{.markup--code .markup--p-code} function has two loops.
If we have an input of 4 words, it will execute the inner block 16
times. If we have 9, it will perform counter 81 times and so forth.

```{#b653 .graf .graf--pre .graf-after--p name="b653"}
hasDuplicates([1,2,3,4]);// n: 4, counter: 16
```

and with n size 9:

```{#ad67 .graf .graf--pre .graf-after--p name="ad67"}
hasDuplicates([1,2,3,4,5,6,7,8,9]);// n: 9, counter: 81
```

\

### Bubble sort {#ea6b .graf .graf--h3 .graf-after--p name="ea6b"}

We want to sort the elements in an array. One way to do this is using
bubble sort as follows:

```{#8043 .graf .graf--pre .graf-after--p name="8043"}
function sort(n) {  for (let outer = 0; outer < n.length; outer++) {    let outerElement = n[outer];
```

```{#7f41 .graf .graf--pre .graf-after--pre name="7f41"}
for (let inner = outer + 1; inner &lt; n.length; inner++) {  let innerElement = n[inner];
```

```{#6e9d .graf .graf--pre .graf-after--pre name="6e9d"}
  if(outerElement &gt; innerElement) {    // swap    n[outer] = innerElement;    n[inner] = outerElement;    // update references    outerElement = n[outer];    innerElement = n[inner];  }}
```

```{#22d8 .graf .graf--pre .graf-after--pre name="22d8"}
}return n;}
```

You might also notice that for a very big `n`{.markup--code
.markup--p-code}, the time it takes to solve the problem increases a
lot. Can you spot the relationship between nested loops and the running
time? When a function has a single loop, it usually translates into a
running time complexity of O(n). Now, this function has 2 nested loops
and quadratic running time: O(n2).

### O(n\^c) — Polynomial time {#155f .graf .graf--h3 .graf-after--p name="155f"}

Polynomial running is represented as O(nc), when `c > 1`{.markup--code
.markup--p-code}. As you already saw, two inner loops almost translate
to O(n2) since it has to go through the array twice in most cases. Are
three nested loops cubic? If each one visit all elements, then yes!

Usually, we want to stay away from polynomial running times (quadratic,
cubic, nc, etc.) since they take longer to compute as the input grows
fast. However, they are not the worst.

### Triple nested loops {#c93d .graf .graf--h3 .graf-after--p name="c93d"}

Let’s say you want to find the solutions for a multi-variable equation
that looks like this:

> _3x + 9y + 8z = 79_

> \

This naïve program will give you all the solutions that satisfy the
equation where `x`{.markup--code .markup--p-code}, `y`{.markup--code
.markup--p-code}, and `z`{.markup--code .markup--p-code} \<
`n`{.markup--code .markup--p-code}.

```{#d887 .graf .graf--pre .graf-after--p name="d887"}
function findXYZ(n) {  const solutions = [];
```

```{#0ccc .graf .graf--pre .graf-after--pre name="0ccc"}
for(let x = 0; x < n; x++) {for(let y = 0; y < n; y++) {for(let z = 0; z < n; z++) {if( 3x + 9y + 8*z === 79 ) {solutions.push({x, y, z});}}}}
```

```{#0475 .graf .graf--pre .graf--empty .graf-after--pre name="0475"}

```

```{#29ac .graf .graf--pre .graf--empty .graf-after--pre name="29ac"}

```

```{#3781 .graf .graf--pre .graf-after--pre name="3781"}
return solutions;}
```

```{#dce2 .graf .graf--pre .graf--empty .graf-after--pre name="dce2"}

```

```{#9f73 .graf .graf--pre .graf--empty .graf-after--pre name="9f73"}

```

```{#188f .graf .graf--pre .graf-after--pre name="188f"}
console.log(findXYZ(10)); // => [{x: 0, y: 7, z: 2}, ...]
```

```{#5b94 .graf .graf--pre .graf--empty .graf-after--pre name="5b94"}

```

```{#2493 .graf .graf--pre .graf--empty .graf-after--pre name="2493"}

```

This algorithm has a cubic running time: `O(n^3)`{.markup--code
.markup--p-code}.

\*\* Note:\*\* We could do a more efficient solution to solve
multi-variable equations, but this works to show an example of a cubic
runtime.

### O(log n) — Logarithmic time {#af98 .graf .graf--h3 .graf-after--p name="af98"}

Logarithmic time complexities usually apply to algorithms that divide
problems in half every time. For instance, let’s say that we want to
look for a book in a dictionary. As you know, this book has every word
sorted alphabetically. If you are looking for a word, then there are at
least two ways to do it:

Algorithm A:

1.  Start on the first page of the book and go word by word until you
    find what you are looking for.

Algorithm B:

1.  Open the book in the middle and check the first word on it.
2.  If the word you are looking for is alphabetically more significant,
    then look to the right. Otherwise, look in the left half.
3.  Divide the remainder in half again, and repeat step \#2 until you
    find the word you are looking for.

Which one is faster? The first algorithms go word by word _O(n)_, while
the algorithm B split the problem in half on each iteration _O(log n)_.
This 2nd algorithm is a binary search.

### Binary search {#e26a .graf .graf--h3 .graf-after--p name="e26a"}

Find the index of an element in a sorted array.

If we implement (Algorithm A) going through all the elements in an
array, it will take a running time of `O(n)`{.markup--code
.markup--p-code}. Can we do better? We can try using the fact that the
collection is already sorted. Later, we can divide it in half as we look
for the element in question.

```{#fb6f .graf .graf--pre .graf--empty .graf-after--p name="fb6f"}

```

```{#38d3 .graf .graf--pre .graf-after--pre name="38d3"}
function indexOf(array, element, offset = 0) {  // split array in half  const half = parseInt(array.length / 2);  const current = array[half];
```

```{#920e .graf .graf--pre .graf-after--pre name="920e"}
if(current === element) {return offset + half;} else if(element > current) {const right = array.slice(half);return indexOf(right, element, offset + half);} else {const left = array.slice(0, half)return indexOf(left, element, offset);}}
```

```{#2631 .graf .graf--pre .graf--empty .graf-after--pre name="2631"}

```

```{#383e .graf .graf--pre .graf--empty .graf-after--pre name="383e"}

```

```{#27f2 .graf .graf--pre .graf-after--pre name="27f2"}
// Usage example with a list of names in ascending order:const directory = ["Adrian", "Bella", "Charlotte", "Daniel", "Emma", "Hanna", "Isabella", "Jayden", "Kaylee", "Luke", "Mia", "Nora", "Olivia", "Paisley", "Riley", "Thomas", "Wyatt", "Xander", "Zoe"];console.log(indexOf(directory, 'Hanna')); // => 5console.log(indexOf(directory, 'Adrian')); // => 0console.log(indexOf(directory, 'Zoe')); // => 18
```

```{#6c06 .graf .graf--pre .graf--empty .graf-after--pre name="6c06"}

```

```{#fa7b .graf .graf--pre .graf--empty .graf-after--pre name="fa7b"}

```

Calculating the time complexity of `indexOf`{.markup--code
.markup--p-code} is not as straightforward as the previous examples.
This function is recursive.

There are several ways to analyze recursive algorithms. For simplicity,
we are going to use the `Master Method`{.markup--code .markup--p-code}.

### Master Method for recursive algorithms {#e8ce .graf .graf--h3 .graf-after--p name="e8ce"}

Finding the runtime of recursive algorithms is not as easy as counting
the operations. This method helps us to determine the runtime of
recursive algorithms. We are going to explain this solution using the
`indexOf`{.markup--code .markup--p-code} function as an illustration.

When analyzing recursive algorithms, we care about these three things:

- The runtime of the work done outside the recursion (line 3–4):
  `O(1)`{.markup--code .markup--li-code}
- How many recursive calls the problem is divided (line 11 or 14):
  `1`{.markup--code .markup--li-code} recursive call. Notice only one
  or the other will happen, never both.
- How much `n`{.markup--code .markup--li-code} is reduced on each
  recursive call (line 10 or 13): `1/2`{.markup--code
  .markup--li-code}. Every recursive call cuts `n`{.markup--code
  .markup--li-code} in half.

1.  The Master Method formula is the following:

> _T(n) = a T(n/b) + f(n)_

> \

where:

- `T`{.markup--code .markup--li-code}: time complexity function in
  terms of the input size `n`{.markup--code .markup--li-code}.
- `n`{.markup--code .markup--li-code}: the size of the input. duh? :)
- `a`{.markup--code .markup--li-code}: the number of sub-problems. For
  our case, we only split the problem into one subproblem. So,
  `a=1`{.markup--code .markup--li-code}.
- `b`{.markup--code .markup--li-code}: the factor by which
  `n`{.markup--code .markup--li-code} is reduced. For our example, we
  divide `n`{.markup--code .markup--li-code} in half each time. Thus,
  `b=2`{.markup--code .markup--li-code}.
- `f(n)`{.markup--code .markup--li-code}: the running time outside the
  recursion. Since dividing by 2 is constant time, we have
  `f(n) = O(1)`{.markup--code .markup--li-code}.

1.  Once we know the values of `a`{.markup--code .markup--li-code},
    `b`{.markup--code .markup--li-code} and `f(n)`{.markup--code
    .markup--li-code}. We can determine the runtime of the recursion
    using this formula:

> _nlogba_

> \

This value will help us to find which master method case we are solving.

For binary search, we have:

nlogba = nlog21 = n0 = 1

1.  Finally, we compare the recursion runtime from step 2) and the
    runtime `f(n)`{.markup--code .markup--li-code} from step 1). Based
    on that, we have the following cases:

_Case 1_: Most of the work done in the recursion.

If `nlogba`{.markup--code .markup--p-code} \> `f(n)`{.markup--code
.markup--p-code},

then runtime is:

> O(nlogba)

> \

_Case 2_: The runtime of the work done in the recursion and outside is
the same

If `nlogba`{.markup--code .markup--p-code} === `f(n)`{.markup--code
.markup--p-code},

then runtime is:

> O(nlogba log(n))

> \

_Case 3_: Most of the work is done outside the recursion

If `nlogba`{.markup--code .markup--p-code} \< `f(n)`{.markup--code
.markup--p-code},

then runtime is:

> O(f(n))

> \

Now, let’s combine everything we learned here to get the running time of
our binary search function `indexOf`{.markup--code .markup--p-code}.

### Master Method for Binary Search {#9322 .graf .graf--h3 .graf-after--p name="9322"}

The binary search algorithm slit `n`{.markup--code .markup--p-code} in
half until a solution is found or the array is exhausted. So, using the
Master Method:

> _T(n) = a T(n/b) + f(n)_

> \

1.  Find `a`{.markup--code .markup--li-code}, `b`{.markup--code
    .markup--li-code} and `f(n)`{.markup--code .markup--li-code} and
    replace it in the formula:

- `a`{.markup--code .markup--li-code}: the number of sub-problems. For
  our example, we only split the problem into another subproblem. So
  `a=1`{.markup--code .markup--li-code}.
- `b`{.markup--code .markup--li-code}: the factor by which
  `n`{.markup--code .markup--li-code} is reduced. For our case, we
  divide `n`{.markup--code .markup--li-code} in half each time. Thus,
  `b=2`{.markup--code .markup--li-code}.
- `f(n)`{.markup--code .markup--li-code}: the running time outside the
  recursion: `O(1)`{.markup--code .markup--li-code}.

Thus,

> _T(n) = T(n/2) + O(1)_

> \

1.  Compare the runtime executed inside and outside the recursion:

- Runtime of the work done outside the recursion: `f(n)`{.markup--code
  .markup--li-code}. E.g. `O(1)`{.markup--code .markup--li-code}.
- Runtime of work done inside the recursion given by this formula
  `nlogba`{.markup--code .markup--li-code}. E.g.
  O(`nlog21`{.markup--code .markup--li-code}) = O(`n0`{.markup--code
  .markup--li-code}) = `O(1)`{.markup--code .markup--li-code}.

1.  Finally, getting the runtime. Based on the comparison of the
    expressions from the previous steps, find the case it matches.

As we saw in the previous step, the work outside and inside the
recursion has the same runtime, so we are in case 2.

> _O(nlogba log(n))_

> \

Making the substitution, we get:

O(nlog21 log(n))

O(n0 log(n))

O(log(n)) 👈 this is the running time of a binary search

### O(n log n) — Linearithmic {#505e .graf .graf--h3 .graf-after--p name="505e"}

Linearithmic time complexity it’s slightly slower than a linear
algorithm. However, it’s still much better than a quadratic algorithm
(you will see a graph at the very end of the post).

Examples of Linearithmic algorithms:

- Efficient sorting algorithms like merge sort, quicksort, and others.

### Mergesort {#f808 .graf .graf--h3 .graf-after--li name="f808"}

What’s the best way to sort an array? Before, we proposed a solution
using bubble sort that has a time complexity of O(n2). Can we do better?

We can use an algorithm called `mergesort`{.markup--code
.markup--p-code} to improve it. This is how mergesort works:

1.  We are going to divide the array recursively until the elements are
    two or less.
2.  We know how to sort two items, so we sort them iteratively (base
    case).
3.  The final step is merging: we merge in taking one by one from each
    array such that they are in ascending order.

Here’s the code for merge sort:

```{#06e9 .graf .graf--pre .graf-after--p name="06e9"}
/** * Sort array in asc order using merge-sort * @example *    sort([3, 2, 1]) => [1, 2, 3] *    sort([3]) => [3] *    sort([3, 2]) => [2, 3] * @param {array} array */function sort(array = []) {  const size = array.length;  // base case  if (size < 2) {    return array;  }  if (size === 2) {    return array[0] > array[1] ? [array[1], array[0]] : array;  }  // slit and merge  const mid = parseInt(size / 2, 10);  return merge(sort(array.slice(0, mid)), sort(array.slice(mid)));}
```

```{#6d8a .graf .graf--pre .graf-after--pre name="6d8a"}
/**
```

```{#0e50 .graf .graf--pre .graf--empty .graf-after--pre name="0e50"}

```

```{#aeab .graf .graf--pre .graf--empty .graf-after--pre name="aeab"}

```

- Merge two arrays in asc order
- @example
- merge([2,5,9], [1,6,7]) =\> [1, 2, 5, 6, 7, 9]
- @param {array} array1
- @param {array} array2
- \

```{#a282 .graf .graf--pre .graf--empty .graf-after--li name="a282"}

```

As you can see, it has two functions, `sort`{.markup--code
.markup--p-code} and `merge`{.markup--code .markup--p-code}. Merge is an
auxiliary function that runs once through the collection
`a`{.markup--code .markup--p-code} and `b`{.markup--code
.markup--p-code}, so it’s running time is O(n). Let’s apply the Master
Method to find the running time.

### Master Method for Mergesort {#80d9 .graf .graf--h3 .graf-after--p name="80d9"}

We are going to apply the [Master Method that we explained
above](https://github.com/bgoonz/2emulate/blob/master/most-popular-algorithms-time-complexity-every-programmer-should-know-free-online-tutorial-course/index.md#Master-Method-for-recursive-algorithms)
to find the runtime:

1.  Let’s find the values of: `T(n) = a T(n/b) + f(n)`{.markup--code
    .markup--li-code}
2.  \

- `a`{.markup--code .markup--li-code}: The number of sub-problems is 2
  (line 20). So, `a = 2`{.markup--code .markup--li-code}.
- `b`{.markup--code .markup--li-code}: Each of the sub-problems
  divides `n`{.markup--code .markup--li-code} in half. So,
  `b = 2`{.markup--code .markup--li-code}
- `f(n)`{.markup--code .markup--li-code}: The work done outside the
  recursion is the function `merge`{.markup--code .markup--li-code},
  which has a runtime of `O(n)`{.markup--code .markup--li-code} since
  it visits all the elements on the given arrays.

1.  \

Substituting the values:

> _T(n) = 2 T(n/2) + O(n)_

> \

1.  Let’s find the work done in the recursion: `nlogba`{.markup--code
    .markup--li-code}.

nlog22

n1 = n

1.  Finally, we can see that recursion runtime from step 2) is O(n) and
    also the non-recursion runtime is O(n). So, we have the [case
    2](https://github.com/bgoonz/2emulate/blob/master/most-popular-algorithms-time-complexity-every-programmer-should-know-free-online-tutorial-course/index.md#Case-2-The-runtime-of-the-work-done-in-the-recursion-and-outside-is-the-same) :
    `O(nlogba log(n))`{.markup--code .markup--li-code}

_O(nlog22 log(n))_

_O(n1 log(n))_

_O(n log(n))_ 👈 this is running time of the merge sort

### O(2\^n) — Exponential time {#115b .graf .graf--h3 .graf-after--p name="115b"}

Exponential (base 2) running time means that the calculations performed
by an algorithm double every time as the input grows.

Examples of exponential runtime algorithms:

- Power Set: finding all the subsets on a set.
- Fibonacci.
- Travelling salesman problem using dynamic programming.

### Power Set {#31c0 .graf .graf--h3 .graf-after--li name="31c0"}

To understand the power set, let’s imagine you are buying a pizza. The
store has many toppings that you can choose from, like pepperoni,
mushrooms, bacon, and pineapple. Let’s call each topping A, B, C, D.
What are your choices? You can select no topping (you are on a diet ;),
you can choose one topping, or two or three or all of them, and so on.
The power set gives you all the possibilities (BTW, there 16 with four
toppings, as you will see later)

Finding all distinct subsets of a given set. For instance, let’s do some
examples to try to come up with an algorithm to solve it:

```{#1d54 .graf .graf--pre .graf-after--p name="1d54"}
123
```

```{#592b .graf .graf--pre .graf--empty .graf-after--pre name="592b"}

```

```{#6d1e .graf .graf--pre .graf-after--pre name="6d1e"}
powerset('') // =>  ['']powerset('a') // => ['', 'a']powerset('ab') // => ['', 'a', 'b', 'ab']
```

```{#514f .graf .graf--pre .graf--empty .graf-after--pre name="514f"}

```

Did you notice any pattern?

- The first returns an empty element.
- The second case returns the empty element + the 1st element.
- The 3rd case returns precisely the results of the 2nd case + the
  same array with the 2nd element `b`{.markup--code .markup--li-code}
  appended to it.

What if you want to find the subsets of `abc`{.markup--code
.markup--p-code}? Well, it would be precisely the subsets of ‘ab’ and
again the subsets of `ab`{.markup--code .markup--p-code} with
`c`{.markup--code .markup--p-code} appended at the end of each element.

As you noticed, every time the input gets longer, the output is twice as
long as the previous one. Let’s code it up:

```{#4721 .graf .graf--pre .graf-after--p name="4721"}
12345678910111213
```

```{#28fb .graf .graf--pre .graf--empty .graf-after--pre name="28fb"}

```

```{#c3ed .graf .graf--pre .graf-after--pre name="c3ed"}
function powerset(n = '') {  const array = Array.from(n);  const base = [''];
```

```{#0d67 .graf .graf--pre .graf-after--pre name="0d67"}
const results = array.reduce((previous, element) => {const previousPlusElement = previous.map(el => {return ${el}${element};});return previous.concat(previousPlusElement);}, base);
```

```{#3d76 .graf .graf--pre .graf--empty .graf-after--pre name="3d76"}

```

```{#bd3c .graf .graf--pre .graf--empty .graf-after--pre name="bd3c"}

```

```{#df41 .graf .graf--pre .graf-after--pre name="df41"}
return results;}
```

```{#6f0b .graf .graf--pre .graf--empty .graf-after--pre name="6f0b"}

```

```{#84d4 .graf .graf--pre .graf--empty .graf-after--pre name="84d4"}

```

If we run that function for a couple of cases we will get:

```{#fd5b .graf .graf--pre .graf-after--p name="fd5b"}
123456789101112
```

```{#d236 .graf .graf--pre .graf--empty .graf-after--pre name="d236"}

```

```{#c4a1 .graf .graf--pre .graf-after--pre name="c4a1"}
powerset('') // ...// n = 0, f(n) = 1;powerset('a') // , a...// n = 1, f(n) = 2;powerset('ab') // , a, b, ab...// n = 2, f(n) = 4;powerset('abc') // , a, b, ab, c, ac, bc, abc...// n = 3, f(n) = 8;powerset('abcd') // , a, b, ab, c, ac, bc, abc, d, ad, bd, abd, cd, acd, bcd...// n = 4, f(n) = 16;powerset('abcde') // , a, b, ab, c, ac, bc, abc, d, ad, bd, abd, cd, acd, bcd...// n = 5, f(n) = 32;
```

```{#b795 .graf .graf--pre .graf--empty .graf-after--pre name="b795"}

```

As expected, if you plot `n`{.markup--code .markup--p-code} and
`f(n)`{.markup--code .markup--p-code}, you will notice that it would be
exactly like the function `2^n`{.markup--code .markup--p-code}. This
algorithm has a running time of `O(2^n)`{.markup--code .markup--p-code}.

\*\* Note:\*\* You should avoid functions with exponential running times
(if possible) since they don’t scale well. The time it takes to process
the output doubles with every additional input size. But exponential
running time is not the worst yet; others go even slower. Let’s see one
more example in the next section.

### O(n!) — Factorial time {#22c8 .graf .graf--h3 .graf-after--p name="22c8"}

Factorial is the multiplication of all positive integer numbers less
than itself. For instance:

> _5! = 5 x 4 x 3 x 2 x 1 = 120_

> \

It grows pretty quickly:

> _20! = 2,432,902,008,176,640,000_

> \

As you might guess, you want to stay away, if possible, from algorithms
that have this running time!

Examples of O(n!) factorial runtime algorithms:

- Permutations of a string.
- Solving the traveling salesman problem with a brute-force search

Let’s solve the first example.

### Permutations {#0a66 .graf .graf--h3 .graf-after--p name="0a66"}

Write a function that computes all the different words that can be
formed given a string. E.g.

```{#6733 .graf .graf--pre .graf-after--p name="6733"}
123
```

```{#4cd3 .graf .graf--pre .graf--empty .graf-after--pre name="4cd3"}

```

```{#5089 .graf .graf--pre .graf-after--pre name="5089"}
getPermutations('a') // => [ 'a']getPermutations('ab') // =>  [ 'ab', 'ba']getPermutations('abc') // => [ 'abc', 'acb', 'bac', 'bca', 'cab', 'cba' ]
```

```{#cc86 .graf .graf--pre .graf--empty .graf-after--pre name="cc86"}

```

How would you solve that?

A straightforward way will be to check if the string has a length of 1.
If so, return that string since you can’t arrange it differently.

For strings with a length bigger than 1, we could use recursion to
divide the problem into smaller problems until we get to the length 1
case. We can take out the first character and solve the problem for the
remainder of the string until we have a length of 1.

```{#bc83 .graf .graf--pre .graf-after--p name="bc83"}
1234567891011
```

```{#a6bf .graf .graf--pre .graf--empty .graf-after--pre name="a6bf"}

```

```{#5b1f .graf .graf--pre .graf-after--pre name="5b1f"}
function getPermutations(string, prefix = '') {  if(string.length <= 1) {    return [prefix + string];  }
```

```{#fee0 .graf .graf--pre .graf-after--pre name="fee0"}
return Array.from(string).reduce((result, char, index) => {const reminder = string.slice(0, index) + string.slice(index+1);result = result.concat(getPermutations(reminder, prefix + char));return result;}, []);}
```

```{#5f41 .graf .graf--pre .graf--empty .graf-after--pre name="5f41"}

```

```{#3e45 .graf .graf--pre .graf--empty .graf-after--pre name="3e45"}

```

If print out the output, it would be something like this:

```{#cef9 .graf .graf--pre .graf-after--p name="cef9"}
12345678
```

```{#bf9c .graf .graf--pre .graf--empty .graf-after--pre name="bf9c"}

```

```{#160a .graf .graf--pre .graf-after--pre name="160a"}
getPermutations('ab') // ab, ba...// n = 2, f(n) = 2;getPermutations('abc') // abc, acb, bac, bca, cab, cba...// n = 3, f(n) = 6;getPermutations('abcd') // abcd, abdc, acbd, acdb, adbc, adcb, bacd...// n = 4, f(n) = 24;getPermutations('abcde') // abcde, abced, abdce, abdec, abecd, abedc, acbde...// n = 5, f(n) = 120;
```

```{#9f2b .graf .graf--pre .graf--empty .graf-after--pre name="9f2b"}

```

I tried with a string with a length of 10. It took around 8 seconds!

```{#5711 .graf .graf--pre .graf-after--p name="5711"}
1234
```

```{#5c1b .graf .graf--pre .graf--empty .graf-after--pre name="5c1b"}

```

```{#d941 .graf .graf--pre .graf-after--pre name="d941"}
time node ./lib/permutations.js## getPermutations('abcdefghij') // => abcdefghij, abcdefghji, abcdefgihj, abcdefgijh, abcdefgjhi, abcdefgjih, abcdefhgij...## // n = 10, f(n) = 3,628,800;## ./lib/permutations.js  8.06s user 0.63s system 101% cpu 8.562 total
```

```{#dd23 .graf .graf--pre .graf--empty .graf-after--pre name="dd23"}

```

I have a little homework for you:

> _Can you try with a permutation with 11 characters? ;) Comment below
> on what happened to your computer!_

> \

### All running complexities graphs {#762b .graf .graf--h3 .graf-after--blockquote name="762b"}

We explored the most common algorithms running times with one or two
examples each! They should give you an idea of how to calculate your
running times when developing your projects. Below you can find a chart
with a graph of all the time complexities that we covered:

![](https://cdn-images-1.medium.com/max/800/0*4FY5xkjVIZDxoMEM.png)

\