Lower bound and worst case scenario

Question

We know that the lower bound is the minimum amount of work needed to solve a problem. So for a given problem say x it has the best algorithm ( the most efficient algorithm to solve this problem ) say algorithm y, then the lower bound efficiency calculated from this algorithm y is the least time this problem x can be solved through . So why do we calculate the lower bound efficiency for this algorithm on the worst case input ? why not on the best case input ? I mean lower bound is the minimum amount of work which therefore occurs on the best case scenario . Every time I see a decision tree algorithm problem to solve the lower bound of some sorting algorithm , the usual word is always mentioned "the worst case lower bound is blah blah blah" which confuse me so much ! Someone please fix my understanding :( .

Answer 1

When analyzing algorithms it makes little sense to consider the best-case scenario as it is very often trivial and not very informative.

You can convince yourself that almost every algorithm can be adapted to have a best-case complexity of $O(n)$, where $n$ is the size of the input, by simply running a preliminary check that verifies if the input instance belongs to some class of instances for which the solution is trivial.

Just to give a concrete example: the best case for every sorting algorithm can be made $O(n)$ if you just check whether the input sequence of numbers is already sorted.

The focus is often on the worst-case complexity. Once you decide that you want to compare algorithms with respect to their worst-case complexity, it also makes sense to ask how quickly a problem can be solved.

It is usually impossible to give a sharp bound to the time needed to solve a problem, therefore one seeks upper and lower bound.

An upper bound of $O(f(n))$ tells you that there is some algorithm that solves the problem in $O(f(n))$ worst-case time.

A lower bound of $\Omega(g(n))$ tells you that no conceivable algorithm can take $o(g(n))$ time to solve the problem.

Just to be clear: a lower bound on the time needed to solve a problem is expressed as a function of the input size $n$ and is the smallest amount of work that is necessary to solve all instances of size $n$. Intuitively (not a formal definition) you can think of it as $\min_{A \in \mathcal{A}} \max_{I \in \mathcal{I}_n} T(A,I)$ where $\mathcal{A}$ is the set of all possible algorithms that solve your problem, $\mathcal{I}_n$ is the set of all instances of size $n$, and $T(A,I)$ is the time needed by $A \in \mathcal{A}$ to solve instance $I \in \mathcal{I}_n$.

What you seem to have in mind instead is $\min_{A \in \mathcal{A}} \min_{I \in \mathcal{I}_n} T(A,I)$.

A lower bound for a problem is useful to establish how "hard" that problem is to solve (problems that require more time to solve are harder, this would make little sense if we looked at the easiest instances instead), and to measure how far an algorithm is from being optimal. For example Merge Sort solves the sorting problem in the optimal amount of time because its running time (asymptotically) matches the $\Omega(n \log n)$ lower bound for the sorting problem (in the comparison-based model).

Answer 2

"lower bound" can be applied for each scenario and individually not meaningful! (lower bound of what?) As we analyzed the worst-case scenario most of the time as time complexity of an algorithm, hence, "lower bound" is applied for the worst-case scenario (not the best case). In other words, as the time complexity is explaining for the worst-case scenario, "lower bound" for the time complexity will be applied to the worst-case scenario.