Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question

migrated from stackoverflow.com Nov 29 '11 at 6:53

This question came from our site for professional and enthusiast programmers.

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
If you know bounds on the values and the distribution of the inputs you can do a probabilistic complexity discussion. –  Patrick Nov 29 '11 at 8:23

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.