08-19-2017, 04:20 PM
(This post was last modified: 08-19-2017, 04:23 PM by etberryhill.)

In proving a tight lower bound for a class of algorithms, one tries to establish, over all possible algorithms:

Lets say you take the class of comparison sort algorithms. The best case for bubble, insertion, selection, quick & merge sort are n, n, n^2, nlogn and nlogn, respectively. If you take the worst possible best case, then you have a lower bound as n^2. But, insertion, bubble, merge, and quick sort perform better in their best cases; therefore, this doesn't actually bound the entire class of algorithms from the bottom. On the other hand, if you take the best possible best case, you have a lower bound of n, which is not asymptotically tight compared to algorithms like selection, merge, and quick sort.

Anyone have the correct answer or any thoughts?

- the worst possible best case

- the worst possible worst case

- the best possible best case

- the best possible worst case

Lets say you take the class of comparison sort algorithms. The best case for bubble, insertion, selection, quick & merge sort are n, n, n^2, nlogn and nlogn, respectively. If you take the worst possible best case, then you have a lower bound as n^2. But, insertion, bubble, merge, and quick sort perform better in their best cases; therefore, this doesn't actually bound the entire class of algorithms from the bottom. On the other hand, if you take the best possible best case, you have a lower bound of n, which is not asymptotically tight compared to algorithms like selection, merge, and quick sort.

Anyone have the correct answer or any thoughts?