Big-O Notation

Big O Notation in JavaScript:

Big O Notation is a mathematical way of measuring the performance of algorithms in terms of their time and space complexity. It provides a way to describe how the performance of an algorithm grows as the size of the input grows. By analyzing the performance of an algorithm, we can make informed decisions about which algorithms to use in different situations.

In JavaScript, we can use Big O Notation to describe the performance of functions and algorithms written in the language. Big O Notation is represented using the capital letter "O" followed by a mathematical expression in parentheses.

Examples of Big O Notations:

O(n): Linear time complexity. The time taken by the algorithm grows linearly with the size of the input.

O(1): Constant time complexity. The time taken by the algorithm does not change as the size of the input grows.

O(n^2): Quadratic time complexity. The time taken by the algorithm grows as the square of the size of the input.

O(2^n): This is considered to be a very slow-growing function, and algorithms with this time complexity are usually impractical for inputs of moderate size or larger.

O(log n): Logarithmic time complexity. The time taken by the algorithm grows logarithmically with the size of the input.

It is important to note that Big O Notation describes the upper bound of the performance of an algorithm. This means that the running time of the algorithm may be less than what is described by the Big O Notation, but it will never be more.

Let's consider an example in JavaScript to understand the concept of Big O Notation better.

O(n):

Consider the following code that calculates the sum of all elements in an array:

The time complexity of this function can be described as O(n), as the time taken by the function grows linearly with the size of the input array. This means that if the input array has 100 elements, the function will take 100 operations to calculate the sum. If the input array has 1000 elements, the function will take 1000 operations to calculate the sum.

O(1):

An example of an algorithm with O(1) time complexity in JavaScript is a function that retrieves the value of an element in an array using its index. The running time of this function does not change as the size of the array grows, as it only requires a single operation to retrieve the value of an element. Here's an example:

In this function, the time taken to retrieve the value of an element from the array is constant and does not depend on the size of the array. This means that the time complexity of the function is O(1). Regardless of whether the array has 10 elements or 10 million elements, the function will always take the same amount of time to retrieve the value of an element.

O(n^2):

An example of an algorithm with O(n^2) time complexity in JavaScript is a function that finds all pairs of elements in an array that sum up to a specific target value. The running time of this function grows quadratically with the size of the array, as it requires nested loop operations to check all possible combinations of elements. Here's an example:

In this function, the time taken to find all pairs of elements in the array that sum up to the target value grows quadratically with the size of the array. If the array has 10 elements, the function will take 10 * 10 = 100 operations to find all pairs. If the array has 100 elements, the function will take 100 * 100 = 10,000 operations to find all pairs. The time complexity of the function is O(n^2), as the running time grows quadratically with the size of the array.

O(2^n):

An example of an algorithm with O(2^n) time complexity in JavaScript is a function that solves the recursive problem of generating all subsets of a set. The running time of this function grows exponentially with the size of the set, as it generates all possible combinations of elements in the set. Here's an example:

In this function, the time taken to generate all subsets of a set grows exponentially with the size of the set. If the set has 3 elements, the function will take 7 operations to generate all subsets (2^3 = 8). If the set has 4 elements, the function will take 15 operations to generate all subsets (2^4 = 16). The time complexity of the function is O(2^n), as the running time grows exponentially with the size of the set.

O(log n):

An example of an algorithm with O(log n) time complexity in JavaScript is a function that performs a binary search on a sorted array. The running time of this function grows logarithmically with the size of the array, as it repeatedly splits the array in half to find the target value. Here's an example:

In this function, the time taken to find the target value in the array grows logarithmically with the size of the array. If the array has 10 elements, the function will take 3 operations to find the target value (2^3 = 8). If the array has 100 elements, the function will take 7 operations to find the target value (2^7 = 128). The time complexity of the function is O(log n), as the running time grows logarithmically with the size of the array.

Big-O Complexity Chart:

I hope it is useful for you :)