Understanding the Complexity of Algorithms: A Deep Dive into Big O Notation with JavaScript

Hi!! It’s been a while since I published articles, due to events, lectures, work and so on.

But I’m coming back slowly! But how does it work, as I always ask? Everthing okay? all in peace? I hope you are doing well!

Today I want to present you very different content, it may be a bit complicated at first, but in many interviews (for big techs) these questions are often asked. Algorithm complexity analysis!

This is such an important concept! If you’ve never dealt with algorithm complexity analysis or the big O in an academic setting, rest assured! I’ll try to address it in a simple way so you understand! But I’m not going to delve too deeply into the subject, because that would take an entire year of study.

Big O

Big O is the language and metric we use to describe the efficiency of algorithms. Sometimes we need to describe whether our algorithm is efficient, and this analysis is important when looking for performance or evaluating whether our algorithm is efficient.

Imagine the following scenario: you have a file on a hard drive and you need to send it to your friend who lives across the country. You need to get the file to your friend as soon as possible. How should you send it?

Some people will suggest: FTP? E-mail? Google Drive?
If it’s a small file, you’re definitely right. It would probably take 5-10 hours to get to the airport, catch a plane and deliver it to your friend in person.

But what if the file were really large. For example 1TB? It may take more than a day for the file to be transferred electronically. It would probably be much faster to fly it across the country.

This is what the concept of asymptotic runtime, or big O time, means.

O(1) would be the example of delivery by plane. O(1) regarding the size of the file. Time is constant.

O(n) would be the example using an electronic transfer. where N is the size of the file. This means that the time to transfer the file increases linearly with the size of the file.

The green line is O(n) and the blue line is O(1).

There are many more durations than this. Some of the most common are O(log n), O(n * log n), O(n), O(nˆ2), O(2ˆn).

Best case, worst case and expected case

We can actually describe our runtime for an algorithm in three different ways:

Imagine the quick sort algorithm:

function quickSort(arr) {

    if (arr.length  1) {
        return arr;
    }


    const pivot = arr(arr.length - 1);
    const left = ();
    const right = ();

    for (let i = 0; i  arr.length - 1; i++) {
        if (arr(i)  pivot) {
            left.push(arr(i));
        } else {
            right.push(arr(i));
        }
    }

    return (...quickSort(left), pivot, ...quickSort(right));
}

For now, don’t be afraid of a resurrection. Quick Sort chooses a random element as a “pivot” and then swaps the values in the array so that the element smaller than the pivot appears before elements larger than the pivot. This gives a “partial sort”. It then recursively sorts the left and right sides using a similar process.

Best case: if all elements are equal, quick sorting will only go through the array once on average. This is O(n).
Worst case: What if we’re really unlucky and the pivot is repeatedly the largest element in the array? In this case, our recursion does not divide the array in half and iterate on each half. It only reduces the subarray by one element. This will degenerate to an O(nˆ2) running time.

Space complexity

Time is not the only thing that matters in an algorithm. We may also worry about the amount of memory or space. Imagine we are working with low memory devices such as IoT.

Space complexity is a parallel concept with time complexity. If we need to create an array of size N, it will require O(n) space. If we need a two-dimensional (matrix) array of nxn, it requires O(n^2) space.

You’ve probably already seen these errors 👀:

Stack overflow
Memory overflow

Also stack space in the number of resurgent calls:

function sum(n) {
 if (n  0)
  return 0;

 return n + sum(n-1);
}

For example, such a code would take O(n) time and O(n) space.

Recursive running times

You’ve probably heard of Fibonacci in mathematics.
The Fibonacci sequence is a series of numbers where each number is the sum of the two previous ones. It usually starts with 0 and 1. The sequence looks like this:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

Now the algorithm:

function fibonacci(n) {
 if (n  1)
  return 1;

 return fibonacci(n-1) + fibonacci(n-1);
}

Many people will see the two calls for one reason or another fibonacci and jump to O(nˆ2). This is completely wrong.

The space complexity of this algorithm will be O(n). Even though we have O(2^n) nodes in the tree total, only O(n) exists at any time.

What is the running time of the code below?

function foo(array) {
 let sum = 0;
 let product = 1;

 array.forEach(item => {
  sum += item;
 });

 array.forEach(item => {
  product *= item;
 });

 console.log(`${sum}, ${product}`);
}

If you answer O(n). Yes, you’re right! The fact that we go through the array twice doesn’t matter.

Now another example:

function printPairs(array) {
  for(let i = 0; i  array.length; i++) {
   for(let j = 0; j array.length; j++) {
    console.log(`${array(i)} , ${array(j)}`);
   }
  }
}

The running time is O(n^2).

So now you can understand these concepts of time and space complexity analysis of algorithms! Of course, I have many other concepts that I haven’t covered here, such as Big Theta, Big Omega, Amortized Time, trees, and more complex recursion.

But this is a difficult concept! And now you understand when asked about the time or space complexity of an algorithm.

That’s it folks! I hope you liked it!
If I help you, please like this post and follow me on my social media!

Linkedin: https://www.linkedin.com/in/kevin-uehara/
Instagram: https://www.instagram.com/uehara_kevin/
Twitter: https://x.com/ueharaDev
Github: https://github.com/kevinuehara
dev.to: https://dev.to/kevin-uehara
Youtube: https://www.youtube.com/@ueharakevin/