sage pawn
Hi,
Big O notation (O) describes the upper bound of the algorithm's time complexity. It represents the maximum amount of time an algorithm will take to run in relation to the input size.
Big Omega notation (Ω) on the other hand, describes the lower bound of the algorithm's time complexity. It represents the minimum amount of time an algorithm will take to run in relation to the input size.
Big Theta notation (Θ) represents the tight bound of an algorithm's time complexity, providing both upper and lower bounds.
Note: The asymptotic notation is not related to the best/worst case of an algorithm. Most people think Big-O is used for the upper bound so it is for the worst case, Omega is for the lower bound so it is for the best case, NO. Any notation can be used for best/worst-case scenarios in an algorithm.
So if we look at the Linear search algorithm we can say to find a key element, the best case takes minimum time while the worst case would take maximum time.
Best case - the searching key element present at the first index
Best case Time - 1 constant time O(1) or Ω(1) or Θ(1). All are correct.
Worst case - the searching key element present at the last element
Worst case time - n O(n) or Ω(n) or Θ(n). All are correct.
Average case - All possible case time / no of cases
Average case time - (n + 1)/2 . it also belongs to n class. O(n) or Ω(n) or Θ(n). All are correct
