# Thread: Asymptotic estimate

1. ## 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++;

2. 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?

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

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

5. 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.)

Popular pages Recent additions