Eduardo Perez Regin’s Reviews > An Introduction to the Analysis of Algorithms > Status Update

Remember the steps to analyze running time. O-notation provides a way to express an upper bound, the Ω-notation provides a way to express a lower bound; and the Θ-notation provides a way to express matching upper and lower bounds. Merge sort is O(NlogN) worst-case performance can provide a guarantee on the performance characteristics of the algorithm no matter what the input is.