Best Upper Bound & Best Lower Bound of an Algorithm
- by Nayefc
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?