Asymptotic estimate

Im suppose to give the asymptotic estimate (that is the most precise) for the number of steps as a function of n. Assum the worst case data! I know what this program does but I have no idea how to figure out the answer.

Code:

bool Found = false; i = 0;
while(!Found && (i <n))
if(A[i] == key) Found = true;
else++;

So count how many times something happens. What if n is 5? How many times do you do _something_? What if n is 10? What if n is 20? What if n is 80? How does this number depend on n?

The worst case would be something happens to n, n number of times!

Well after you fix that algorithm, you might want to read this article.

Originally Posted by jturner38

The worst case would be something happens to n, n number of times!

It's not quite that you're doing something to n (you're doing a comparison i<n, you're doing a comparison A[i] == key). But yes, you can go through the loop n times, so the algorithm is O(n). (We don't worry about the fact that's it's really 2n -- we can have any (constant) multiplier we want without affecting the big O function.)