Thread: Asympotic Estimates of Run-Times

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

    Asympotic Estimates of Run-Times

    Im trying to learn the Best Case, Average case, and Worse case Data. I kinda understand them and I kinda don't.

    Example:

    Code:
    for(i = 1; i<n, i++)
    for(j=0; j<n-1; j++)
        if(A[j] > A[i]
           {Switch = A[j];
                  A[j] = A[j+1];
                  A[j+1] = Switch;
            }
    Would the Worse case be n^2 number of steps?

  2. #2
    Password:
    Join Date
    Dec 2009
    Location
    NC
    Posts
    587
    Think about how many times those loops will execute. It looks to me as if you're 1 off. Maybe (n +/- 1)^2 ?

    EDIT: Also, note that there's no way for the loop to exit before the worst case is met, therefore best = average = worst.
    Last edited by User Name:; 11-30-2010 at 11:53 PM.

  3. #3

  4. #4
    Registered User
    Join Date
    Feb 2009
    Location
    Indiana
    Posts
    99
    If Im 1 off. then (n-1)^2? Would that be correct since I could have a case where I might have to switch?

  5. #5
    Registered User
    Join Date
    Feb 2009
    Location
    Indiana
    Posts
    99
    Actually it should be (n+1)^2 because (n+1)^2 = n^2 + O(n)?

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by jturner38 View Post
    Im trying to learn the Best Case, Average case, and Worse case Data. I kinda understand them and I kinda don't.

    Example:

    Code:
    for(i = 1; i<n, i++)
    for(j=0; j<n-1; j++)
        if(A[j] > A[i]
           {Switch = A[j];
                  A[j] = A[j+1];
                  A[j+1] = Switch;
            }
    Would the Worse case be n^2 number of steps?
    Yes, and so would the Best and Average cases, albeit with different constant factors when executed in practice.

    That code is borken by the way, both in terms of not compiling and not doing what one might expect.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Something about probablility
    By mike_g in forum A Brief History of Cprogramming.com
    Replies: 116
    Last Post: 03-13-2008, 05:33 PM
  2. calculating the mode
    By bigggame in forum C Programming
    Replies: 10
    Last Post: 06-13-2006, 03:04 AM
  3. Counting the number of times a loop has run
    By CConfusion in forum C Programming
    Replies: 1
    Last Post: 04-07-2006, 10:23 AM
  4. Program to run in Dos only
    By ihsir in forum C++ Programming
    Replies: 2
    Last Post: 01-19-2002, 06:16 PM
  5. Trying to make rand different per program run
    By Dreamerv3 in forum C++ Programming
    Replies: 6
    Last Post: 01-18-2002, 03:26 AM