# Big O Notation in JavaScript

“What is Big O Notation?” that is a very common job interview question for developers. In short, it is the mathematical expression of how long an algorithm takes to run depending on how long is the input, usually talking about the worst case scenario.

In practice, we use Big O Notation to classify algorithms by how they respond to changes in input size, so algorithms with the same growth rate are represented with the same Big O Notation. The letter O is used because the rate of growth of a function is also called order of the function.

It is usually acceptable that your first version of an algorithm is not the most efficient solution but the fastest to code, assuming it will be replaced for a more efficient one in future versions. This is a very common practice in agile development, especially in test-driven-development.

Sometimes we want to focus on using less memory instead of (or in addition to) using less time (iterations) and usually there’s a trade-off between saving time and saving space. You can also see this kind of balance between saving read time and saving disk space, or when comparing relational (normalized) and non-relational (denormalized) databases.

Let’s now explore the most common types of Big O Notations, we will be using JavaScript (ECMA6) as our reference language but the same principle applies to any other.

# Constant-Time Algorithm

O(1) — “Order 1”

On this order, regardless of the complexity (number of items), the time (iterations) is constant.

You will see this on algorithms that returns an element in an already known position of an array, regardless kind or length.

Example code:

`const getLast = items =>  items[items.length-1];`

Example case:

`getLast(['a', 'b', 'c', 'd']); // d (1 iteration)getLast(['a', 'b', 'c', 'd', 'e', 'f', 'g']);// g(1 iteration)`

# Linear-Time Algorithm

O(N) — “Order N”

In this order, the worst case time (iterations) grows on par with the number of items.

In other words, for N elements we will require N iterations.

Example code:

`const findIndex = (items, match) => {  for (let i = 0, total = items.length; i < total; i++)    if (items[i] == match)      return i;   return -1;};`

Example case:

`const array= ['a', 'b', 'c', 'd'];findIndex(array, 'a'); // 0  (1 iteration - best case)findIndex(array, 'd'); // 3  (4 iterations - worst case)findIndex(array, 'e'); // -1 (4 iterations - worst case)`

O(N 2 ) — “Order N squared”

For this kind of order, the worst case time (iterations) is the square of the number of inputs. The time grows exponentially related to the number of inputs.

Example code:

`const buildSquareMatrix = items => {  let matrix = [];  for (let i = 0, total = items.length; i < total; i++){     matrix[i] = [];    for (let j = 0, total = items.length; j < total; j++)      matrix[i].push(items[j]);  }  return matrix;};`

Example case:

`buildSquareMatrix(['a', 'b', 'c']); /* 9 iterations for 3 elements, returns:[  ['a', 'b', 'c'],  ['a', 'b', 'c'],  ['a', 'b', 'c']]/*`

# Logarithmic-Time Algorithm

O(n log n) — “Order N log N”

These are the holy grail of search/sort algorithms, they are usually the most efficient approach when dealing with large collections. Instead of looking through the components one by one, they split the data in chunks and discard a large amount on every iteration, usually the half, or log base 2.

Assuming we are using a log base 2, we could -ideally- find a specific element in a collection of one million elements using less than 20 iterations, if we scale the size of the collection to a billion we would require only less than 30 iterations.

With big data being more common every day, it’s easy to see the advantage of this kind of algorithms since the larger the collection, the more relative efficiency they provide.

The most popular of this algorithms is the Quicksort algorithm, which can be used to find a specific element or sort a list very efficiently. Another popular example of this order is the Merge-Sort algorithm. We will explore these algorithms on future articles.

Example code:

`const quickSort = list => {  if (list.length < 2)     return list;  let pivot = list;  let left  = [];   let right = [];  for (let i = 1, total = list.length; i < total; i++){    if (list[i] < pivot)      left.push(list[i]);    else      right.push(list[i]);  }  return [    ...quickSort(left),     pivot,     ...quickSort(right)  ];};`

Example case:

`quickSort( ['q','a','z','w','s','x','e','d','c','r']);// ["a", "c", "d", "e", "q", "r", "s", "w", "x", "z"]`

And that’s how we covered the most common types of algorithms, I invite you to read more about search & sorting algorithms.

Happy coding!

Bibliography:

Big O Search Algorithms in JavaScript. — Bradley Braithwaite

Written by

Written by

## César Antón Dorantes

#### Google Developer Expert | Senior Software Engineer ## Cesar’s Tech Insights

#### Tutorials, Articles and Reviews about Software Development & Technology

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just \$5/month. Upgrade