How to Learn Algorithmic Complexity with JavaScript

Overview

In this article, we'll explore what terms like "quadratic" and "n log(n)" mean in the context of algorithms.

In the examples that follow, I will refer to these two arrays, one containing 5 elements and the other containing 50 elements. I’ll also use JavaScript’s handy performance API to measure the difference in execution time.

const smArr = [5, 3, 2, 35, 2];

const bigArr = [5, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3, 2, 35, 2];

What is Big O notation?

Big O notation is a way to express the overall increase in difficulty of a computational task as the size of the data set increases. Although there are other notations, big O notation is generally the most commonly used because it focuses on the worst-case scenario, which is easier to quantify and consider. The worst case scenario means the one that requires the most operations to complete the task; if you can unscramble the cube in under a second, you can't say you did the best job if you only twisted it once.

This is very useful as you get further into algorithms, because as you write code you understand this relationship and know where the time is being spent.

As you learn more about Big O notation, you may see different variations of the following diagram. We want to keep the complexity as low as possible, preferably not exceeding O(n).

O(1)

This is the ideal situation, no matter how many projects there are, whether it's one or a million, the amount of time to complete will remain the same. Most operations that perform a single operation are O(1). Writing data to an array, getting an item at a specific index, adding child elements, etc. will all take the same amount of time regardless of the length of the array.

const a1 = performance.now();
smArr.push(27);
const a2 = performance.now();
console.log(`Time: ${a2 - a1}`); // Less than 1 Millisecond


const b1 = performance.now();
bigArr.push(27);
const b2 = performance.now();
console.log(`Time: ${b2 - b1}`); // Less than 1 Millisecond

O(n)

By default, all loops grow linearly because there is a one-to-one relationship between the size of the data and the time to complete. So if you have 1,000 array items, it will take 1,000 times as long.

const a1 = performance.now();
smArr.forEach(item => console.log(item));
const a2 = performance.now();
console.log(`Time: ${a2 - a1}`); // 3 Milliseconds

const b1 = performance.now();
bigArr.forEach(item => console.log(item));
const b2 = performance.now();
console.log(`Time: ${b2 - b1}`); // 13 Milliseconds

O(n^2)

Exponential growth is a trap we all fall into. Do you need to find a matching pair for every item in the array? Putting loops within loops is a great way to turn an array of 1,000 items into a million operation searches that will make your browser unresponsive. It is better to do 2,000 operations in two separate loops than to do a million operations using a doubly nested loop.

const a1 = performance.now();
smArr.forEach(() => {
    arr2.forEach(item => console.log(item));
});
const a2 = performance.now();
console.log(`Time: ${a2 - a1}`); // 8 Milliseconds


const b1 = performance.now();
bigArr.forEach(() => {
    arr2.forEach(item => console.log(item));
});
const b2 = performance.now();
console.log(`Time: ${b2 - b1}`); // 307 Milliseconds

O(log n)

I think the best metaphor for logarithmic growth is to imagine looking up a word like "notation" in the dictionary. You don't search term by term, but first find the "N" section, then the "OPQ" page, and then search the list alphabetically until you find a match.

With this "divide and conquer" approach, the time to find something will still vary with the size of the dictionary, but it's nowhere near O(n). Because it searches progressively more specific parts without looking at the bulk of the data, searching a thousand items might require less than 10 operations, and a million items might require less than 20 operations, maximizing your efficiency.

In this example, we can do a simple quick sort.

const sort = arr => {
  if (arr.length < 2) return arr;

  let pivot = arr[0];
  let left = [];
  let right = [];

  for (let i = 1, total = arr.length; i < total; i++) {
    if (arr[i] < pivot) left.push(arr[i]);
    else right.push(arr[i]);
  };
  return [
    ...sort(left),
    pivot,
    ...sort(right)
  ];
};
sort(smArr); // 0 Milliseconds
sort(bigArr); // 1 Millisecond

O(n!)

The worst possibility is factorial growth. The classic example is the traveling salesman problem. If you are traveling between many cities of varying distances, how do you find the shortest route between all the cities back to your starting point? A brute force approach would be to check all possible route distances between each city, which is a factorial and will quickly get out of hand.

Because this problem can quickly become very complex, we will demonstrate this complexity with a short recursive function. This function multiplies a number by itself and then subtracts 1 from the number. Each number in the factorial is calculated this way until it reaches 0, and each recursive layer adds its product to the original number.

Factorials are simply the products starting at 1 and going up to that number. Then 6! is 1x2x3x4x5x6 = 720.

const factorial = n => {
  let num = n;

  if (n === 0) return 1
  for (let i = 0; i < n; i++) {
    num = n * factorial(n - 1);
  };

  return num;
};
factorial(1); // 2 Milliseconds
factorial(5); // 3 Milliseconds
factorial(10); // 85 Milliseconds
factorial(12); // 11,942 Milliseconds

I had intended to display factorial(15), but values ​​above 12 were too many and crashed the page, demonstrating why this needs to be avoided.

Conclusion

It seems like an indisputable fact that we need to write performant code, but I’m sure almost every developer has created at least double or even triple nested loops because “it just works.” Big O notation is essential in expressing and thinking about complexity in a way that we never had before.

The above is the details of how to learn algorithm complexity with JavaScript. For more information about JS algorithm complexity, please pay attention to other related articles on 123WORDPRESS.COM!