Big O Notation and Algorithms in JavaScript

Introduction to Big O Notation

Big O notation shows the number of operations an algorithm will perform, its complexity, and how quickly it will grow. It will never show the execution time of the algorithm.

These are the six main types of complexity we find in Big O notation:

Constant O(1): The number of executions will always be the same regardless of the input size "n". It is the best complexity since the size of the input data does not affect it.

Logarithmic O(log n): The number of executions increases logarithmically in proportion to the input size "n". Typically, the executions involve dividing the input data into smaller parts.

Linear O(n): The number of executions increases linearly with the input size "n". The executions will be equal to the input size, so the larger the input, the more executions will be required.

Exponential O(2^n): In this case, the number of executions doubles in relation to the input size "n". If with an input X we get 20 executions, with double that input we will get 400 executions. While not the worst, it is recommended to avoid this complexity, especially for large datasets.

Quadratic O(n^2): In this case, the number of executions increases quadratically with the input size "n". This occurs when there are nested loops. It is one of the worst complexities, along with factorial complexity.

Factorial O(n!): In this case, the number of executions increases factorially with the input size "n". Along with quadratic complexity, it is one of the worst and becomes nearly impossible to handle with large amounts of data.

---

Let's look at a couple of examples of search algorithms in JavaScript where we can measure two of the listed complexities:

1. Linear Search

Linear search goes through the array element by element until it finds the desired value or reaches the end of the array.

The complexity of this algorithm is O(n), or linear. It increases in proportion to the size of the array, meaning the larger the array, the more executions will be required.

In this code example, we return the index of the element when it matches the value we are searching for, and -1 when the value is not found.

function linearSearch(array, value) {

    for (let i = 0; i < array.length; i++) {
        if (array[i] === value) return i
    }

    return -1
}

Some JavaScript array methods that use linear search:

• indexOf
• lastIndexOf
• includes
• find
• findIndex
• some
• every

2. Binary Search

First, it's important to note that this search algorithm can only be performed on sorted arrays.

What happens here is that the array is divided into two halves, then the value we're searching for is compared to determine which half it belongs to. The algorithm iterates with the same operation over the relevant half until it finds the value.

The complexity of this algorithm is O(log n), or logarithmic. In the following code example, at each step, the algorithm halves the search space until it finds the desired value or determines that it is not present. We return the index where the value is found, or -1 if the value is not in the array.

function binarySearch(array, value) {
    let start = 0;
    let end = array.length - 1;
    let middle = Math.floor((start + end) / 2);

    while(array[middle] !== value && start <= end) {
        if(value < array[middle]) end = middle - 1;
        else start = middle + 1;

        middle = Math.floor((start + end) / 2);
    }

    return array[middle] === value ? middle : -1;
}

In Conclusion

Big O notation is a standardized way of measuring the efficiency of different algorithms, focusing on predicting their behavior as the input size grows.

It's important to emphasize the need to dive deeper into these concepts, especially if we aim for excellence when handling large amounts of data.

Resources:

• Image of the chart taken from FreeCodeCamp.org