Best Upper Bound & Best Lower Bound of an Algorithm
Posted
by
Nayefc
on Programmers
See other posts from Programmers
or by Nayefc
Published on 2011-11-29T01:12:20Z
Indexed on
2011/11/29
10:08 UTC
Read the original article
Hit count: 577
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?
© Programmers or respective owner