Algorithm and Complexities
1
If we construct an algorithm with worst-case complexity theta of n ^ 2 I can have as a counterpart a better case complexity for this algorithm with big n ^ 2?
asked by anonymous 26.02.2016 / 22:45
1 answer
3
Yes. But I would use a different notation to talk about the best case.
When we write that the worst case is O(f) we mean that the time spent in the worst case is asymptotically less than or equal to this function. But the "less or equal" is not good for discussing a better case.
What we really want is a notation that means "greater or equal." The conventional notation for this is Ω(f) (big-omega).
Returning to the original question: If the worst case is O(n^2) , the best case may be Ω(n^2) . It is enough that your algorithm is one whose execution time depends only on the size of the input, but not on its specific value.
26.02.2016 / 22:53