Can someone explain the difference between Big O, Big Omega, and Big theta ? I u
ID: 3912275 • Letter: C
Question
Can someone explain the difference between Big O, Big Omega, and Big theta ? I understand that big O is upper bound, Big Omega is lower bound and Big theta is tight bound. But how do you know which to use when analyzing an algorithm? And why do these matter ? Can someone explain the difference between Big O, Big Omega, and Big theta ? I understand that big O is upper bound, Big Omega is lower bound and Big theta is tight bound. But how do you know which to use when analyzing an algorithm? And why do these matter ?Explanation / Answer
In order to solve a problem in computer science we can generally write program in many languages like C, C++, python, etc. But, before writing a program we prefer to write an informal description of the solution which is called algorithm. Suppose we have a problem P1 and we want to solve it by making a program in C. There might be many ways to solve the problem or we say many algorithms to solve the problem, but we select the algorithm which takes less time to execute and uses less memory or we can say we select the algorithm which is more efficient.
For that, we do analysis on each algorithm for its (1) time complexity or efficiency and (2) space complexity. Time complexity of an algorithm is basically running time of an algorithm as a function of input size. To express time complexity of an algorithm we use a notation called asymptotic notation. Big Oh(O), Big Omega and Big Theta are asymptotic notations.
In practice, we are not interested in finding best case time of an algorithm, we are always interested in finding worst case time of an algorithm for any input size. So, we use Big-O, not Big-Omega in general. We use Big-Theta when worst case and best case times both are same which means that for any input size the algorithm will take the same time. So, in such cases we go for Theta.