# Understanding Algorithmic Complexity (Big-O Notation)?

When analyzing the performance of an algorithm, we use Landau notation (often called "Big-O") to express algorithmic complexity.

This notation allows us to evaluate how the execution time evolves according to the size of the input.

Let's see what this means, and the differences between complexities like O(n), O(n²) and O(log(n)).

The notation

In the O(n) notation:

• O represents the complexity of the function we are evaluating
• n represents the number of iterations our code will have to perform before stopping

For example, to iterate through a list of 3 elements [”a”, “b”, “c”], we will have to run a loop of 3 iterations.

So the complexity to go through the entire list will be O(3).

Except that in practice, for algorithms whose efficiency matters, we don't know the number of elements to process in advance, so we use the variable n!

To summarize, if n is the number of elements of a list, then if we have to go through each element of the list, the complexity of this algorithm will be O(n).

As you'll have understood, our goal is to ensure that the complexity of our algorithm doesn't increase as fast as the number of elements to process…

But this isn't always possible!

Let's go together through a few examples of complexity to know and understand to optimize the processing time of your code.

Complexities to know

O(n): Linear complexity

The O(n) notation indicates that an algorithm has a complexity proportional to the size of the input.

In other words, the execution time doesn't grow faster than a linear function of the input size n.

Traversing a list of n elements often requires O(n) operations.

function display(arr) {
    for (const el of arr) {
        console.log(el);
    }
}

Here, each element is traversed only once.

So if the list contains 10 elements, 10 operations are performed, and if it contains 1000, then 1000 operations will be performed.

The execution time therefore grows linearly with n.

O(n²): Quadratic complexity

The O(n²) notation indicates that an algorithm has a complexity proportional to the square of the input size.

This means that if the input size doubles, the number of operations performed is multiplied by four.

An algorithm using two nested loops is generally O(n²).

function compareElements(arr) {
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length; j++) {
            console.log(arr[i], arr[j]);
        }
    }
}

Here, each element is compared to all the others.

If the list contains 10 elements, 100 iterations are performed, but with 1,000 elements, 1,000,000 iterations take place.

Quadratic growth is therefore more resource-intensive than linear growth.

Selection sort or insertion sort algorithms, for example, have an O(n²) complexity in the worst case, which makes them inefficient for very large inputs.

O(log(n)): Logarithmic complexity

The O(log(n)) notation means that the execution time grows proportionally to the logarithm of the input size.

This means that if n increases exponentially, the execution time only increases linearly.

A classic example of an O(log(n)) algorithm is binary search (or dichotomous search), used to search for an element in a sorted list.

function binarySearch(arr, target) {
    let left = 0, right = arr.length - 1;

    while (left <= right) {
        let middle = Math.floor((left + right) / 2);

        if (arr[middle] === target) {
            return middle;
        } else if (arr[middle] < target) {
            left = middle + 1;
        } else {
            right = middle - 1;
        }
    }
    return -1;
}

In this algorithm, instead of going through all the elements one by one, we split the list in two at each iteration. Thus, for a list of 1,000 elements, instead of doing 1,000 iterations, we do only about log₂(1,000) ≈ 10.

This optimization is extremely effective for large values of n.

Ignoring constants

When we talk about algorithmic complexity, we accept that O(2n) = O(n).

But why do we ignore multiplicative constants?

The O(n) notation represents an upper bound (asymptotic bound) up to a constant. And mathematically, O(2n) = O(n) because there exists a constant c such that 2n ≤ c * n for any sufficiently large n.

So O(2n), O(100n) or O(0.5n) are all equivalent to O(n) in asymptotic notation.

Conclusion

O(n) is a notation for quickly understanding the complexity of an algorithm, which will strongly influence its performance based on the number of elements n.

• O(n) means that the algorithm has linear complexity.
• O(n²) indicates that the execution time grows quadratically with the input size, which can quickly become inefficient for large values of n.
• O(log(n)) is a logarithmic complexity, which is extremely efficient for large inputs because the number of operations grows very slowly.