In the field of computer science, big O notation is one of the most commonly used mathematical notations! 

Did you know?

It tells how well any algorithm will perform under a situation. 

Besides this, we can analyse the efficiency of an algorithm while learning about its time and space complexity and the storage and resources needed to run the algorithm. 

The big O notation is described as a language that we may use for how long the algorithm will help to run the time complexity or space complexity of an algorithm. 

This concept mainly focuses on the upper bound runtime of various types of algorithms which can also be termed as the worst case algorithms. 

In this blog, we have discussed in detail about big O notation!

Let’s get started!

Asymptotic Notations 

The performance of any algorithm can change with that of the change in the required input size. This is where the big O notation comes into scenes. An asymptotic notation is known to describe the run time of an algorithm where the input will move towards the limiting value. 

There will be an asymptotic analysis where you can change the size of your input with the performance of your algorithm. 

Big O Notation - an overview 

In data structure, big O notation is described to express the arithmetic complexity that is used in the algebraic terms. This will denote the upper bound of any algorithm’s runtime to calculate the time or amount of memory that is required to execute the algorithm based on its desired input value. 

In simpler terms, big O notation is also described as a limiting behaviour of the function where the arguments will bend towards the value or infinity. It also describes the required complexity of the notation of codes by using algebraic terms. 

The mathematical definition 

Consider the needed functions g[n] and f[n]. F and g are called the unbound set of real numbers G[n] is called the positive number for the larger value of given n. 

F is also called the O[g] where c>0 with that of natural number n0

You can also write it as:

F[n] = O [ g [ n]] 

Where n is denoted by infinity

Linear search example 

Let's talk about the following example:

We can start searching for the number eight that ranges from 1 till 8. 

The first strategy would be to start with that first number of given arrays by moving it with one till it moves towards the target numbers. The algorithm steps that you will follow in this case are:

First start from the beginning The compare the target value with the target value Then move towards the next value Then reach till the end of a given list 

In round one, you can choose 1 number which is not right. Then you can eliminate that and move towards 2. If it also is not correct, move towards other numbers till eight. 

Though, in the case of the worst scenario, this approach may not be efficient. You can check all the single numbers in a given list until you get the answer. This method is also known as linear search. 

Here, big O notation is used with that of time complexity O[N]. This time complexity would be directly related to your input size. The algorithm in this case will take the additional steps towards the data element.

Runtime analysis of algorithm with big O notation 

To analyse the performance of an algorithm, you should calculate worst case complexities of desired algorithms. O[1] would be called the constant running time. 

This constant running time would be touted as the fastest running algorithm which is taken by the algorithm for varied input sizes. On the other hand, the given constant running time would be considered as the ideal running time that you may achieve in a rare way. 

As the run time performance of the given algorithm that is dependent on the n input size. For required linear search, the runtime complexity would be O[n] 

Though, in case of binary search, the runtime complexity would be O[log n ]. But for the bubble sort, insertion sort, selection sort, the runtime complexity in this case would be O[n^c].

The exponential algorithm like hanoi or tower will have the runtime complexity of O[c^n]. However, in the case of heap sort, sort sort and merge sort, the runtime complexity would be O [n log n] 

Analysing the space complexity

For all types of algorithms, you also need to calculate the space complexity. While analysing the runtime performance of your complexity, we can know the execution time that an algorithm is taking. 

You can analyse both the time and space complexity to know about the memory space. Thus, in order to measure the space complexity in case of an algorithm, you need to compare the desired worst case performance of your algorithm. 

You need to perform major two tasks which includes:

Task 1: There will be an implementation of a given program with a particular algorithm as and when it is required.

Task 2: There will be the required size of the input that is denoted by n which is required to know about the memory of each item

To analyse the algorithm:

You can see the range of some outer loops i < n where the order of loops is O[n]Then, for the inner loop, you need to use O[n] The average efficiency in this case would be n/2 with the constant c. But you can ignore the constant in a required ignore For multiplying the given order of your inner or outer loop, you can get the runtime complexity would be O[n^2] 

Wrapping up 

Learn in depth about the big O notation in detail with the help of this blog post. Also learn about the time and space complexity to strengthen your knowledge base.

Happy learning!