java - Empirical analysis for binary search not matching Theoretical Analysis -

i'm doing test binary searches average case. generate random variable , search random variable in different sized arrays using binary search. below code used:

   public static void main(string[] args)      {         //this array keeps track of times of linear search         long[] arraytimetaken = new long[18];          //values of array lengths test         int[] arrayassignvalues = new int[18];         arrayassignvalues[0] = 1000000;         arrayassignvalues[1] = 10000000;         arrayassignvalues[2] = 20000000;         arrayassignvalues[3] = 30000000;         arrayassignvalues[4] = 40000000;         arrayassignvalues[5] = 50000000;         arrayassignvalues[6] = 60000000;         arrayassignvalues[7] = 70000000;         arrayassignvalues[8] = 80000000;         arrayassignvalues[9] = 90000000;         arrayassignvalues[10] = 100000000;         arrayassignvalues[11] = 110000000;         arrayassignvalues[12] = 120000000;         arrayassignvalues[13] = 130000000;         arrayassignvalues[14] = 140000000;         arrayassignvalues[15] = 150000000;         arrayassignvalues[16] = 160000000;         arrayassignvalues[17] = 170000000;          //code runs linear search         (int = 0; < arrayassignvalues.length; i++)          {             float[] arrayexperimenttest = new float[ arrayassignvalues[i]];              //we fill array ascending numbers              (int j = 0; j < arrayexperimenttest.length; j++)              {                 arrayexperimenttest[j] = j;             }              random generator = new random();             int valuetosearchfor = (int) generator.nextint(arrayassignvalues[i]);             system.out.println(valuetosearchfor);             valuetosearchfor = (int) arrayexperimenttest[valuetosearchfor];              //here perform linear search             arraytimetaken[i] = binarysearch(arrayexperimenttest,valuetosearchfor);         }         chartcreate(arraytimetaken);           system.out.println("done");     } 

here code binary search:

 static long binarysearch(float[] arraysearch,int valuefind)     {         system.gc();         long starttime = system.nanotime();          int low = 0;         int high = arraysearch.length-1;         int mid = math.round((low+high)/2);          while (arraysearch[mid] != valuefind )          {                         if (valuefind <arraysearch[mid])              {                 high = mid-1;             }             else             {                 low = mid+1;             }             mid = (low+high)/2;         }         long timetaken = system.nanotime() - starttime;         return timetaken;     } 

now problem results aren't making sense. below graph:

can explain how 1st array takes time? i've run code few times , same graph created every time. java how cache results? can explain result why 1st binary search takes long relativve others though array size tiny compared rest?

it looks you're doing these searches 1 after another, starting lowest values. if that's true, code running slower, because jit compiler won't have had chance warm yet. generally, benchmarking this, want run through relevant code give jit compiler time compile , optimize before real testing.

for more information on jit compiler, read this

you should see this question learn more benchmarking.

another possible cause of slowness jvm still in process of starting up, , running it' own background code while you're timing it, causing slowdown.