HomeAbout MeContact

Big O notation In Javascript

By Gopal Baskota
Published in JavaScript
January 07, 2021
3 min read

Introduction “Big O notation” is a common term used in the programming community. But many developers, especially beginners, are confused with this term. So what is the meaning of big O notation? Is it necessary to write a code? Can we do coding without being familiar with big O notation? Let’s find the answers to these questions in this article.

What is Big O notation?

In simple words, Big O notation is a language used in computer science and programming to explain how an algorithm is performing. “O” in Big O notations stands for Order.

The performance is quantified by time cost and space cost. These are also known as time complexity and space complexity, respectively. Both these complexities are calculated in accordance with the size of input - n.

The time complexity explains the amount of runtime an algorithm is taking to run when the size of input increases. Similarly, for the space complexity, it explains the amount of additional space, relative to the size of the input, an algorithm requires.

But what is the need for Big O notation? Why it is used? The Big O notation is used to choose a suitable algorithm. For every task, we can have different algorithms. We don’t need every one of them. We only need that algorithm that is best for the problem in the terms of time and space complexities. In simple words, we use Big O notation to check the efficiency of an algorithm.

The best example to understand the need for Big O notation is sorting. To sort a list, we have different types of sorting such as bubble sort, merge sort, quick sort, etc. But we only choose which is efficient for the problem.

The complexity is divided into three cases: best, average, and worst.

  1. The best case scenario is when it takes the minimum number of steps to finish a task.
  2. The worst case scenario is when it takes the maximum number of steps to finish a task.

The average case is just ambiguous. Generally, the worst case complexity is used because it is the worst scenario for any input.

Now let’s understand different ways in which the performance of an algorithm is calculated with Big O.

The first one is constant time.

When it takes a constant time to run an algorithm, regardless of the input size, the complexity is O(1). Accessing an array element is an example of O(1). Observe the below code.

let arr1 = [1, 2, 3]
let arr2 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

console.log(arr1[0])
console.log(arr2[0])

In the above code, “arr1” and “arr2” are two arrays with different sizes. Regardless of the size, it will take the same time to access the element at the 0th index.

The second is linear time.

When the time taken by an algorithm to run increases with the increase in the input size, the complexity is O(n). Iteration, insertion, and deletion are examples of O(n). Observe the following code.

let arr1 = [1, 2, 3]
let arr2 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

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

print(arr1)
print(arr2)

In the above code, the function “print” is iterating over both the arrays -“arr1” and “arr2”. As the size of “arr2” is greater than the size of “arr1”, it will take more time to iterate over “arr2” than “arr1”.

Apart from the above two, we have logarithmic time, quadric time, and cubic time

When the time taken by an algorithm to run increases barely with the exponential increase in input, the complexity is O(log n) or logarithmic time. Merge sort such as merge sort is an example of O(log n)

When the calculations run in quadratic time, the complexity is O(n^2) or quadratic time. Sorting such as bubble sort, insertion sort, and selection sort are examples of quadratic time. Conclusion So this was an introduction to Big O notation. Every programming task can be performed in different ways by using different algorithms. But we should choose only that algorithm that is efficient. Big O notation is a great way to measure the efficiency of an algorithm. It is a bit complicated concept. It takes time and practices Big O.


Tags

BigOjavascript
Previous Article
forEach() Method in javascript and how to use it .

Gopal Baskota

Full stack Web Developer

Topics

JavaScript
NodeJs
React Js

Related Posts

javascript algorithms - Insertion sort Explained using Javascript .
January 11, 2021
1 min
© 2021, All Rights Reserved.

Quick Links

Advertise with usAbout UsContact Us

Social Media