The upper bound for a problem is defined to be:

The cost of the best algorithm that we know for the problem
  • The cost of the worst algorithm that we know for the problem
  • The same as the lower bound for the problem
  • The cost of the worst case input for the problem

For a given problem, it is possible to write an algorithm that is as bad as we want. So defining a bound in terms of bad algorithms is not useful.

We look at the worst-case input to determine the worst-case upper bound for an algorithm, not a problem.

To get the upper bound for a problems, we compare the cost for each algorithm that we know.

The upper bound of the problem is the upper bound of the best known algorithm.