Asymptotic lower bounds¶

When considering asymptotic running times, how far from the optimal is, for instance, mergesort? To answer this, we must define the computation model we use. We consider a standard “random access machine” model in which memory locations can be accessed in constant time and in which all memory locations and registers have some fixed bit width. Thus each step can only access and manipulate a fixed number of bits. Let us further assume a “comparisons only” restriction in which

we can compare two elements for (in)equality with \(=\), \(<\), \(\le\), \(>\), or \(\ge\),
but we cannot obtain any other information, such as their binary encodings, about the elements.

For instance, sorting algorithm implementations that only use the Scala Ordered trait interface fall under this assumption. In this “comparisons only model”, we can get the following asymptotic lower bounds for the numbers of comparisons that any algorithm must make in the worst case. As the running time of a sorting algorithm cannot be less than the number of comparisons it makes, in the \(\BigOh\)-notation, these lower bounds apply to the running times as well.

Searching an element in an ordered array must make \(\Omega(\Lg n)\) comparisons in the worst-case.

Thus binary search is, in an asymptotic sense, optimal.
Sorting an array of \(n\) elements requires \(\Omega(n \Lg n)\) comparisons in the worst case.

Therefore, mergesort is, in an asymptotic sense, optimal.

The proofs of these are not included in the course, please see Section 8.1 in Introduction to Algorithms, 3rd ed. (online via Aalto lib) for them.