Are asymptotic notations flawed?

2
votes

The best-case complexity of any algorithm is the minimum amount of time that the algorithm will take to accomplish its task. We know that the best case complexity of algorithms like merger sort, quick sort, etc is Ω(n log(n)), which defines the lower bound of these algorithms.

As we know that in asymptotic notations -

O(n) + O(n log(n)) = O(n log(n))

also,

Ω(n) + Ω(n log(n)) = Ω(n log(n))

So, if in these sorting algorithms, we first traverse the entire array in O(n) time to determine if the array is already sorted in ascending or descending order, then asymptotically their average case and worst case complexities would remain the same. But their best case complexity would now become Ω(n).

Logically there is definitely a flaw in my way of understanding these asymptotic notations otherwise someone would definitely have had pointed this out when Asymptotic notations were being developed or becoming popular to measure sorting algorithms. Am I correct in assuming that this is a plausible flaw in asymptotic notations or am I missing some rule of Asymptotic notations?

2
algorithmsortingtime-complexitycomplexity-theory
"We know that the best case complexity of [comparative sorting] algorithms ... is O(n log(n))" actually the best case is O(n), as you have observed, so your initial assumption is incorrect. You might be thinking of the average case performance, which is indeed O(n log(n)). – Patrick Roberts
@PatrickRoberts in the line that you have quoted, there I am talking about 2 specific algorithms i.e. merge sort and quick sort [comparative sorts] whose best-case complexity is in fact O(n log(n)) [as referenced by my Algorithm books and also by a quick google search]. Hence my initial assumption is correct as I am in fact discussing about comparative sorting algorithms and their best case. – Deekshant
All the statements you make (up to the last paragraph) are technically correct (even if there is no reason to use Omega and O in various places - that implies a misunderstanding on your part). But the last paragraph is a non sequitur. What flaw are talking about? Can you expand on that? Are you surprised that some algorithms have a best-case behaviour that's different from the worst-case behaviour? Are you surprised that one can modify an algorithm such that its best-case behaviour changes but not the worst-case? – Mo B.
"if in these sorting algorithms, we first traverse the entire array in O(n) time to determine if the array is already sorted" then you have a different algorithm with a different best-case time complexity. – kaya3
@MoB. the flaw I am talking about is, that for any sorting algorithm with best-case complexity more than Ω(n), a simple O(n) traversal can be done of the array to determine if the array is already sorted. This would make the best case complexity of all such sorting algorithms Ω(n), thus making the notion of best-case complexity redundant for all these algorithms as it would then be Ω(n) i.e same for all. – Deekshant

2 Answers

2
votes

There are certainly problems with using asymptotic complexity as a measure of speed. First and foremost, obviously constants do matter. 1000n will often be much larger than n log n, and certainly n^1000 is much larger than 2^n for any practical value of n. As it turns out, however, the asymptotic complexity is often a fairly good indicator of an algorithms actual speed.

The problem you raise is also correct, but I wouldn't consider it a problem. It is true that a simple isSorted() check at the start of quicksort reduces its best case complexity to Θ(n), but it is very rare for people to care about best case performance. Indeed, many algorithms for common problems can be modified to be best case linear, but this is just not very useful.

Finally, note that this is not really a flaw in asymptotic notation specifically. Making a random guess and verifying whether the guess was correct (such as by guessing that an array is already sorted) often really does improve best case performance, while having very little effect on the average or worst case, regardless of the notation used.

0
votes

First, you should distinguish in your mind between the case (best, worst, average, etc.) and the bound (upper, lower, O, Omega, Theta, etc.)

Let us focus on Bubble Sort, defined as follows:

if array == null or array.length < 2 then return
do
    swapped = false
    for i = 0 to array.length - 2
        if array[i] > array[i+1] then
            swap(array, i, i+1)
            swapped = true
until not swapped

The best case for this algorithm is a sorted array, in which case the lower (Omega), upper (O) and Theta bounds all agree the runtime is bound by a function of the form f(n) = an; that is, T(n) = O(n). The best case for Bubble Sort is linear.

The worst case for this algorithm is an array in reverse-sorted order. In this case, the runtime is bounded from above and below by a function like g(n) = bn^2; T(n) = O(n^2) in the worst case.

You aren't missing anything and it's perfectly ordinary for algorithms to have different worst-case and best-case runtime bounds. It's also perfectly possible that an algorithm may not optimize for the best case since the best case is typically not the one we are worried about anyway; yes, merge sort could first check to see if the array is sorted, but there are a relatively small number of those over the set of all possible arrays of length N.

Also, you may choose to talk about a lower bound on the worst case, or an upper bound on the best case. These things are not what we typically focus on - instead focusing on upper bound on the worst case, or possibly lower bound on the best case - but the case and the bound are totally separate things and can be combined arbitrarily.