educative.io

Educative

Big O, Big Theta, Big Omega

Is it right

  • Big O - Worst case

  • Big Theta - Averge Case

  • Big Omega - Best Case

Hi @Azizbek_Khushvakov,
Yes, This is the right representation of notations.
Happy learning!

1 Like

Not quite. All three notations can be used for best-case, worst-case, or for average-case as these notations give asymptotic bounds on a function that may correspond to the best-case, the worst-case, or the average-case running time. These notations may often be used in the sense you mention, but they don’t have to be. Let’s take an example.

The best case running time of insertion sort is linear. A linear polynomial is Big-O(n) but it is also Big-Omega (n), and therefore it is also Big-Theta(n). So it would be perfectly legitimate to say “The best-case running time of insertion sort is Big-O(n)”. We don’t typically use the Big-O notation with the best case because that’s not very useful for us. For the best case, a Big-Omega lower bound is more useful for expressing that we can’t do better than this. For the worst case, Big-O is useful because it tells us we can’t do worse than this.

When using these notations to express a fact about a running time (best, worse, average), think about whether you want to say bounded from above (Big-O), bounded from below (Big-Omega), or bounded from both above and below (Big-Theta).