The lower bound for a problem is defined to be:

The best possible cost for any algorithm that solves the problem
  • The cost of the best algorithm that we know for the problem
  • The same as the upper bound for the problem
  • The cost of the best case input for the problem
  • The maximum cost that any algorithm to solve the problem could have

Upper and lower bounds are used to describe to what we know, and we do not always know that these are the same for a given algorithm.

Lower bound refers to the class of inputs that we are considering (best, average, or worst-case). So it does NOT necessarily have anything to do with the best-case input.

The cost of the best algorithm that we know sets a limit on the upper bound of the problem, not the lower bound.

The lower bound refers to the best possible cost (for the class of inputs, such as worst-case) for ANY algorithm that solves the problem.