Rate of Growth Assignment.

[disco990]

Hello everyone!

I have an assignment in my Java class to gauge and compare the "order of growth" of two different sections of code. Below is the actual assignment:

"The following code fragment (adapted from a Java programming book) creates a random permutation of the integers from 0 to N-1. Determine the order of growth of its running time as a function of N. Compare its order of growth with Shuffle.java from Section 1.4."

and here is the code the assignment talks about:

int[] a = new int[N]; 
boolean[] taken = new boolean[N]; 
int count = 0; 
while (count < N) 
{ 
   int r = StdRandom.uniform(N); 
   if (!taken[r]) 
   { 
       a[r] = count; 
       taken[r] = true; 
       count++; 
   } 
} 

My main question is, how do I go about computing the order of growth? and what would that code look like? If you guys could point me in the right direction that would be much appreciated. I'll provide links to some of the other classes if needed:

StdRandom: http://www.cs.princeton.edu/introcs/...StdRandom.java

Shuffle: http://www.cs.princeton.edu/introcs/...t/Shuffle.java

Thanks again!

[chaarmann]

The order of growth means, informally speaking, how much slower your program becomes if you increase the value of N, compared to your other program.

Just call your program with different values of N. Before calling it, measure the time with System.currentTimeMillis(). After it ends, measure the time the same way again. The difference then tells you how long the program needed for execution.

Then do the same with Shuffle.java and compare growth in time of both programs.

[JosAH]

You can also take a bit more analytical approach; for loop pass i (i starting at zero) you have the probability i/n of picking an already taken number, so on average you take p*(i/n)^p == (i/n)/(1-(i/n)) == i/(n-i)+1 turns to complete loop pass i.

Sum that turn over all i in [0,n] and you'll see that if n approaches infinity the sum approaches infinity much faster. Say, for n == 10 you get:

(0/10+1/9+2/8+3/7+4/6+5/5+6/4+7/3+8/2+9/1)+10 turns

The other method only requires n swaps which is equal to the last term of the above sum.

kind regards,

Jos