Calculating run time

Hi, I want to ask about how can I calculate a run time of function.
Consider I have this function :

1
2
3
4
5
6
7
8
9
10
11
int min = N;
for (int i = 0; i < N; i++) {
	Selection.sort(a, a[i].BY_POLAR_ORDER);
	for (int j = 0; j < N; j++) {
		for (int k = j+1; k < N; k++) {
			if (a[j].distanceTo(a[k]) <= 1.0) {
				min = Math.min(min, k - j);
			}
		}
	}
}


So, if say that when the N is 2000 (N=2000), the code run for 30seconds.
Then how long will it run if the input is N?
Can somehow teach me how I can calculate this?
This is my study material for upcoming exam.

Thank you :)
Using ^ to indicate exponentiation:

The outer loop goes N times:
   selection sort is N^2
   The middle loop goes N times:
       The inner loop goes on average N/2 times. (N-1 times down to 1 time)

So N * (N^2 + (N * N/2)) = N * 1.5 N^2 = 1.5 N^3 or O(N^3)

Therefore if N=2000 runs for 30 seconds, N=1000 should run for about 30/12 = 2.5 seconds. N=4000 should run for about 12*30 = 360 seconds = 6 minutes. N=10000 should run for 187.5*30=5625 seconds = 93.75 minutes = 1 hour 33 minutes 45 seconds.
Last edited on
Topic archived. No new replies allowed.