Importance of Big O, Big Ω and Big Θ notation.

Asymptotic

As we know that Big O, Big Ω, and Big Θ are three asymptotic notations that are used to calculate the space and time complexity of an algorithm. But every time we are not going to calculate all three for an algorithm.  

Significance of Big O, Big Ω, and Big Θ notation.

Base on the practical significance of the above notations for a given algorithm:

Big O is going to say the worst-case time or upper bound which means, if we are giving any time complexity in terms of Big O, it says that in any case, your time will not exceed this.

Big is going to say the best case time or lower bound which means, in any case, you can’t achieve better than this. In this notation, we analyze the minimum number of steps that need to be executed. 

Big Θ is going to say the average case time, somewhere in between the worst and best. In this notation, we calculate the average by considering different types of inputs including the best case and the worst case.

In practice, we are not interested in what is the best time the algorithm could execute. We are always interested in what is the worst-case time that will be taken by this algorithm for any input.

Lower Bound < Average Bound < Upper Bound

We use the average case when the best case and worst case both are the same when both cases are taking the same time.

Example: Assume an array of length n.

I want to search for an element using linear search, if the element we want to search is 5, then in base case we can search it in 1 comparison. In 1 step we can find it out.

=> (1) time complexity and it says that you can never go down beyond this.

If I have n elements in the array then I need to compare all the elements in the worst-case O(n) and it says that you can never go beyond this. 

Related post: 


If you like this post and find it useful then you can show your support by donating a small amount from your heart. You can also show your support by following us on Facebook and Twitter.

Post a Comment

Previous Post Next Post