BIG O'NOTATION

Big O notation is one of the most fundamental tools for computer science students to analyze the time and space complexity of an algorithm.
By the end of this article, you'll thoroughly understand Big O notation.

Genrally, there is always more than one way to solve a problem in computer science with different algorithms.Therefore it is highley required to use a method to compare the solution in order to judge which on is better.
With the Time and Space complexity we calculate the Big O of a code/algorith which describes the better algorithm.

What is Big O?

Big O notation is a way to measure an algorithm’s efficiency. It allows us to understand space and time complexity of our code.

It measures the efficieny of your code in it's worst case scenario i.e it describes the behaviour of a function when the argument tends towards the maximum input.

In other words, Big-O addresses one question “How will my algorithm/code behave as my input grows?”.

Big O'Notation is used in two ways:

When talking about Big O Notation it’s important that you understand the concepts of time and space complexity

1.To classify the time complexity(speed) of an algorithm.
2.To classify the space complexity(memory) of an algorithm.

In this article we discuss about Time Complexity.

Time Complexity

It is the amount of time taken by an algorithm to run, as the input increases. It measures the time taken to execute each statement of code in an algorithm.

What causes time complexities?

• Operators(+, -, *, /)
• Comparisons(<, >, ==)
• Loops(for, while)
• Function Calls

Common Time Complexities

• Linear Complexity-- O(n) : The running time of the algorithm increases linearly with the size of the input.
• Constant Complexity-- O(1) : A constant runtime meaning, regardless of the size of the input, the algorithm will have the same runtime.
• Logarithmic Complexity-- O(log n) : O(log n) means that time goes up linearly, while the n goes up exponentially. So if it takes 1 second to compute 10 elements, it will take 2 seconds to compute 100 elements and so on.
• Linearithmic Complexity-- O(n log n) :The running time of the algorithm is as a result of performing a logarithmic operation N times. For example, inserting N number of nodes inside a binary search tree. Each insertion takes O(LogN) time, while the entire algorithm takes linearithmic time.

Here is the Big-O complexity chart :

You can visit [https://www.bigocheatsheet.com/] for more cheat-sheets and informations.

We can take a deeper dive into Linear and Constant time complexities

Linear Time Complexity O(n) :

We can discuss this with an example.
consider a factory of some product which is packing it's products in boxes for shipping to its customers.

Linear time complexity means as the number of elements increases number of operations also increases.

In our case When we have only one product we just need to pack only one box. Same way if we have 1000 products we need to pack 1000 boxes. So here as the products increases number of boxes to pack also increase. That is what linear time complexity

We can take a look at a function :

const packBoxes = (products) => {
  products.forEach(product => console.log(product));
}

Here we are printing just printing the array of products using a loop. So if we have only one 1 product the loop will only work one time. So the time taken will be less. Same way if we have 1000 products in that array it will loop through all those 1000 products. so the time taken will be high

This shows that as input increases the number of operations also increases.

Constant Time Complexity O(1) :

We can consider the same example we've used above.
What if we have 1000 products and a single customer?
Yeah, we just need to pack only one box, no matter how many products you have as if you have only one customer.
This is what Constant complexity means, regardless of the number of inputs only one operation is done

we can take a look at it with another example

const packBoxes = () => (products) {
   console.log(product[0]);
}

In this example we are just printing the first item in the product array. We are not thinking about number of products in that we are just printing the first element from that.
so if we have 1 elemnt or 1000 elements we just need to print the first element. So both will take the same time without considering the number of inputs.

Summary

Big O represents how long an algorithm takes (time complexity) and how much memory it takes(space complexity).

We've only discussed some of the most used time complexities in this article.