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