Complexities
in Algorithm

Asymptotic Notations

Asymptotic Notations are the mathematical tools to represent the time complexity of algorithms. There are three asymptotic notations are most used:

Types of Asymptotic Notations

1)Big Omega notation,2) Theta Notation, 3) Big O notation.

Big Omega Notation are considered as a lower bound of an algorithm. Theta notation bounds a functions from above and below, so it defines exact asymptotic behaviour. Big O notation are considered as a upper bound of an algorithm. In real life we generally most use Big O notation to tell the complexity of an algorithm.

Worst,Average and Best case Time Complexities

We can have three cases to analyze an algorithms:

//This is a code for linear search in an Array
//if x is present then return true,otherwise return false
search(arr,x){
for(var element of arr) {
if(element===x) return true;
}
return false;
}

Worst Case

In real case scenario we usually do worst case analysis. In worst case analysis, we calculate the upper bound on running time of an algo. For linear Search the worst case happens when the element is not present in the array or present at last. In both cases we get the complexity as n(n is the size of the array). Therefore the worst case complexity of linear search is o(n).

Average Case

In average case analysis, we take all possible inputs and calculate computing time for all of the inputs. Then sum the calculated values and divide the sum by total number of inputs. We doesn't use it more in real scenarios. The average case complexity of Linear search would be theta(n)

Best Case

It is totally useless complexity. In this we calculate the lower bound of an algo. So, suppose you find the x in Linear Seach at first point then according to Best case complexity it will be written as o(1).

Important points: