Thread: Average asymptotic run time?

  1. #1
    Registered User
    Join Date
    Aug 2003

    Average asymptotic run time?

    Hi all,

    The following code is from one of the programming classes that I used to attend. This function recursively sums the elements in an array. They said that the a priori complexity of this algorithm is O(n), while the average asymptotic run time is 2n. What I want to know is what is this "average asymptotic run time," how to calculate it, and how it is related to the a priori complexity (The Big Oh notation)? Thanks!

    int sum(int array[], int n) {
    	if (n <= 0) {
    		return (0);
    	return (array[n - 1] + sum(array, n - 1));

  2. #2
    Join Date
    Jul 2005
    The worst-case asymptotic runtime is O(n) (probably what he means by a priori complexity), and the average-case asymptotic runtime is O(n).

    To say something like "2n" is just moronic, well, partially moronic, that's probably your professor being a moron or you not taking complete notes. The reason "2n" means nothing is because what does the "2" mean? 2 microseconds? 2 millenia?

    "Average case asymptotic runtime" refers to the run time in the average case. There are some algorithms that work reasonably well in the average case, but take much more time for certain inputs. For example, quicksort takes O(n log n) in the average case (random ordering of elements), but for certain types of inputs it takes Theta(n * n) time.
    Last edited by Rashakil Fol; 08-03-2005 at 06:50 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Using pointers
    By Big_0_72 in forum C Programming
    Replies: 3
    Last Post: 10-28-2008, 07:51 PM
  2. need help in time zone
    By Gong in forum C++ Programming
    Replies: 2
    Last Post: 01-03-2007, 04:44 AM
  3. The space time continueimnms mm... (rant)
    By Jeremy G in forum A Brief History of
    Replies: 32
    Last Post: 06-27-2004, 01:21 PM
  4. winXP , run time error ???
    By beely in forum Windows Programming
    Replies: 1
    Last Post: 03-13-2003, 03:17 PM
  5. I apologize. Good bye.
    By doubleanti in forum A Brief History of
    Replies: 14
    Last Post: 05-03-2002, 06:51 PM