Thread: Asymptotic estimate

  1. #1
    Registered User
    Join Date
    Feb 2009
    Location
    Indiana
    Posts
    99

    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. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    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. #3
    Registered User
    Join Date
    Feb 2009
    Location
    Indiana
    Posts
    99
    The worst case would be something happens to n, n number of times!

  4. #4
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    Well after you fix that algorithm, you might want to read this article.

  5. #5
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by jturner38 View Post
    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 subscribe to a feed

Similar Threads

  1. Sorting (asymptotic) complexity problem
    By Petike in forum C++ Programming
    Replies: 8
    Last Post: 01-20-2009, 07:15 AM
  2. Algorithmic Complexity + Asymptotic Notations
    By koodoo in forum C Programming
    Replies: 5
    Last Post: 09-03-2006, 02:25 AM
  3. Average asymptotic run time?
    By Ariod in forum C Programming
    Replies: 1
    Last Post: 08-03-2005, 06:47 PM