big theta - gives both an upper and lower bound on the running time of an algorithm. So, if we say running time of algorithm A is theta(n^2), we mean that given any input, the algorithm would take f(n^2) time to complete.
big O - gives an upper bound on the running time of an algorithm. So, if we say run time of A is O(n^2), we mean, given any input size, it will not take more than f(n^2) time to execute A. It may take lesser.
big omega - gives a lower bound. if run time of A is omega(n^2), we mean that it takes no less than f(n^2) time to complete. It may take more.
So, when we say worst case complexity of quick sort is theta(n^2), what we mean is, in the worst case, quick sort always takes f(n^2) time, however large the input size is. It does not say anything about the best case, or the average case !!!
No comments:
Post a Comment