#Algorithm #Performance #Big-O

This article will give you a brief and simple explanation of what the Big-O Notation does.

Introduction

The Big-O notation is a way to describe how efficient a piece of code is. More precisely, it defines how the execution time is affected by a growth of the input.

For Example:

Code Input Size Execution time
A 1 1 sec
A 3 3 sec
A 6 6 sec
B 1 1 sec
B 3 9 sec
B 6 36 sec

In this example, code A is more efficient. When the input size increases, the time increases in a linear fashion. For code B, the time increases in a quadratic fashion.

In that example, we can say that if N is the size of the input:

  • code A is a big-O of N: O(N)
  • code B is a big-O of N2: O(N^2)

More examples

In JavaScript.

Constant complexity

If the time complexity for an algorithm is O(1), it is said to be constant. No matter how big the input, the execution time will always be the same.

Example:

function getFirstElement(array) {
    return array[0];
}

No matter how big the array, the execution time remains the same as we are simply return the first element.

Linear complexity

If the time complexity for an algorithm is O(N), it is said to be linear. The execution times increases linearly with the input size.

Example:

function findMax(array) {
    var length = array.length;
    var index = -1;
    
    while (++index < length) {
        var currentValue = array[index];
        
        if(currentValue != null && (currentMax === undefined || currentValue > currentMax)) {
            var currentMax = currentValue;
        }
    }
    
    return currentMax;
}

In this code, we iterate through the array only once, so the time needed to complete the operation is directly proportional to the array length.

Quadratic complexity

If the time complexity for an algorithm is O(N^2), it is said to be of quadratic growth. The execution time increases linearly with the square of the input size.

Example:


var array1 = ['M', 'a', 'r', 'y'];
var array2 = ['J', 'a', 'c', 'k'];

for(var i = 0; i < array1.length; i = i + 1) {
    for(var j = 0; j < array2.length; j = j + 1) {
        console.log(array1[i] + array2[j]);
    }
}

In this, for each element in array1, we go through all the elements of array2. The time needed to complete the operation is proportional to the square of the arrays’s length.

Note:

  • If both array have the same size, the time complexity is O(N^2)
  • If both array have a different size, the time complexity is O(N.M) (as in N times M, where N and M are the array sizes)

Conclusion

I hope this gives you an idea of what the big-O notation means and is used for.

In our example, we have used it to measure the time complexity, in some cases in can also be used to measure the space complexity (the space used in memory).

#Algorithm #Performance #Big-O