For example, if time complexity of merge sort is O(n log n) then why it is big O not theta or omega. I know the definition of these, but what I do not understand is how to determine the notation based on the definition.
Asked
Active
Viewed 788 times
2
-
2[See this](http://stackoverflow.com/questions/471199/what-is-the-difference-between-%CE%98n-and-on/471206#471206). – ChiefTwoPencils Jun 15 '14 at 04:59
1 Answers
0
For most algorithms, you are basically concerned on the upper bound on its running time. For example, you have some algorithm to sort an array of numbers. Now you would most likely be concerned that how fast will the algorithm run in the worst possible case.
Hence the complexity of merge sort is mostly written as O(nlogn) even when it will be better to express it as theta(nlogn) because theta notation is a more tighter bound. And merge sort runs in theta(nlogn) time because it will always consume this much time no matter what the input is.
You will not find omega notation again mostly because we are concerned with the upper bounds on running time and not the lower bound.
Nikunj Banka
- 11,117
- 16
- 74
- 112