Lecture 383:- Asymptotic Notations Big Oh , Omega , Theta

Asymptotic notations (Big O, Omega, Theta) are used to describe the upper and lower bounds of the running time or space complexity of an algorithm in terms of the input size (n).

1. Big O Notation (O): It represents the upper bound of the growth rate of an algorithm. If an algorithm has a time complexity of O(f(n)), it means the algorithm's running time will not exceed f(n) as the input size (n) grows. Big O notation provides the worst-case time complexity.
2. Omega Notation (Ω): It represents the lower bound of the growth rate of an algorithm. If an algorithm has a time complexity of Ω(g(n)), it means the algorithm's running time will be at least g(n) as the input size (n) grows. Omega notation provides the best-case time complexity.
3. Theta Notation (Θ): It represents both the upper and lower bounds of the growth rate of an algorithm. If an algorithm has a time complexity of Θ(h(n)), it means the algorithm's running time will be between h(n) and some constant multiple of h(n) as the input size (n) grows. Theta notation provides the average-case time complexity.

To understand these notations better, let's consider an example:

Suppose we have an algorithm to find the maximum element in an unsorted array of size n.

The algorithm traverses the array once, comparing each element with the current maximum to find the maximum element.

The time complexity of this algorithm is O(n) because the running time grows linearly with the size of the input array.

The Omega notation for this algorithm is Ω(n) because in the best-case scenario, the algorithm may still need to traverse the entire array to find the maximum element.

The Theta notation for this algorithm is Θ(n) because the upper and lower bounds are both O(n) and Ω(n), indicating that the running time will be proportional to the input size in all cases.

In summary, Big O notation describes the upper bound, Omega notation describes the lower bound, and Theta notation describes both the upper and lower bounds of an algorithm's time or space complexity.