Getting the same running time answer for different input numbers

Question

So far I have done... the first class contains Insertion Sort algorithm

public class Sorting { public static void insertionSort(int[] r) { for ( int i = 1; i < r.length; i = i+1 ) {int v = r[i]; int j = i; while ( j != 0 && r[j-1] > v ) {r[j] = r[j-1]; j = j-1; } r[j] = v; } } }

and here is the second class ...

import java.util.*; public class ExecutionTime{ public static void main(String[] args){ int size=30000; int[] r = new int[size]; int number=1; for(int i=1;i<size;i++){ r[i]=number; number++;} for(int i=1;i<size;i++){ System.out.println(r[i]);} Sorting.insertionSort(r); long result; long startTime = System.nanoTime(); long endTime = System.nanoTime(); result = endTime-startTime; System.out.println("Execution time is " + result + " nanoseconds"); } }

when I set size=15000 and 30000 i get the same answer for both sizes...of course I have executed it many times for each size — Gerta2
– Gerta2, Commented Jan 2, 2014 at 22:20

ashes999 · Accepted Answer · 2014-01-02 22:22:01Z

1

You're not actually timing the sorting:

 Sorting.insertionSort(r); long result; long startTime = System.nanoTime(); long endTime = System.nanoTime(); result = endTime-startTime;

Notice you sort first, then calculate the time difference of, well, not doing anything (there's no code between startTime and endTime are assigned). Instead, do this:

 long result; long startTime = System.nanoTime(); Sorting.insertionSort(r); long endTime = System.nanoTime(); result = endTime-startTime;

This way, endTime - startTime spans the sorting operation.

answered Jan 2, 2014 at 22:22

ashes999

10.2k19 gold badges81 silver badges125 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Gerta2 Over a year ago

Hey...i still don't get it ...after calculating running time, i get these results: n=7500 T(n)=6668618nanosec n=15000, T(n)=10141050.6 n=30000 T(n)=10761703.9 n=60000 T(n)=10970219.6 n=120000 T(n)=18546223.2 Is it ok to have these results? I'm afraid it's not ://

ashes999 Over a year ago

Seems okay for me. What different results were you expecting?

Gerta2 Over a year ago

I don't know I was totally confused after all those experiments and those different results ... now what about when they are in the descending order...insertion sort has the worst case ...and it is n^2..n*n... so are the results I get okay? n=7500 T(n)=12523388...n=15000 T(n)=30953258... n=30000 T(n)=98072540...n=60000 T(n)=561960091...n=120000 T(n)=1465733398

Community · Accepted Answer · 2017-05-23 12:28:30Z

As per Precision vs. accuracy of System.nanoTime() there is no guarantee to how frequently the values it returns will change. Just because 4000 nanoseconds have passed between two times you've called the function does not mean the value has changed.

Precision vs. accuracy at work.

Collectives™ on Stack Overflow

Getting the same running time answer for different input numbers

2 Answers 2

3 Comments

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Linked

Related