Best Upper Bound & Best Lower Bound of an Algorithm

Question

I am studying for a final exam and I came past a question I had on an earlier test.

The questions asks us to find the minimum value in an unsorted array of integers. We must provide the best upper bound and the best lower bound that you can for the problem in the worst case.

First, in such an example, the upper and lower bound are the same (hence, we can talk in terms of Big-Theta). In the worst case, we would have to go through the whole list as the minimum value would be at the end of the list. Therefore, the answer is Big-Theta(n).

Is this a correct & good explanation?

Answer 1

In the worst case, we would have to go through the whole list as the minimum value would be at the end of the list.

You have to go through the whole list in any case, because otherwise you do not know if the current minimum is indeed the absolute minimum. So the algorithm would always require n iterations.

The only exception is if you know bounds on the possible values, for example that the integers are all positive, and you have already found a 1 (then you can stop). That does not change the complexity discussion, though.

• Patrick: If you know bounds on the values and the distribution of the inputs you can do a probabilistic complexity discussion.