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.
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.