Difference between Best Conceivable Runtime vs Best Case Runtime

Question

I have been struggling understanding the difference between between Best Conceivable Runtime and Best Case Runtime. How do you think of between the two? Is Best Case Runtime the optimal runtime? If so, how does one decide on best conceivable time?

Answer 1

The best case runtime means you have an algorithm that solves the problem, and in the best case, that algorithm has a particular time complexity.

For example, the best case runtime for selection sort is O(n²) because it will always do that many operations whatever the array is. On the other hand, the best case runtime for insertion sort is O(n), in the case that the input array is already sorted.

---

The best conceivable runtime is a concept introduced, as far as I know, in the book Cracking the Coding Interview by Gayle Laakmann McDowell. It means you have a problem and you are trying to estimate how efficiently it can be solved; you do not have an algorithm yet, or if you do have an algorithm then you don't know if there is another algorithm that might have a lower asymptotic time.

The best conceivable runtime means it is the best time you can conceive that the problem could possibly be solved in, and it is definitely impossible for the problem to be solved faster than that. It's a quick check you do to rule out certain approaches which couldn't possibly work, because if they did work, they would be too fast.

For example, the problem of sorting cannot be solved in under O(n) average time, because it would take O(n) time just to do the correct writes/swaps to put the elements in their right places. That doesn't mean there is an algorithm which sorts in O(n) average time, just that it's definitely impossible to do better than O(n) on average.

A better argument can show that the best conceivable runtime for a comparison-based sorting algorithm is O(n log n) on average, because each comparison only gives one bit of information about which permutation the input array is in, so you need at least log₂ (n!) comparisons to distinguish between all n! possible permutations. So it's impossible to write a comparison-based sorting algorithm that uses a single loop over the array, and does O(1) work per iteration; we can rule out this possibility when trying to design an algorithm. In this case, there are comparison-based sorting algorithms which meet this asymptotic bound, so it's tight.

So, to some extent there isn't really one "best conceivable runtime" for a given problem, it depends on your ability to prove that a given runtime is a lower bound on all possible algorithms that solve the problem.