time complexity for java arrayList remove(element) -

i trying graph time complexity of arraylist's remove(element) method. understanding should o(n), however, giving me o(1). can point out did wrong here?? thank in advance.

   public static void arraylistremovetiming(){     long starttime, midpointtime, stoptime;     // spin computer until 1 second has gone by, allows     // thread stabilize;     starttime = system.nanotime();     while (system.nanotime() - starttime < 1000000000) {     }     long timestoloop = 100000;     int n;     arraylist<integer> list = new arraylist<integer>();      // fill array 0 10000     (n = 0; n < timestoloop; n++)         list.add(n);      starttime = system.nanotime();     (int = 0; < list.size() ; i++) {         list.remove(i);          midpointtime = system.nanotime();         // run loop capture other cost.         (int j = 0; j < timestoloop; j++) {          }         stoptime = system.nanotime();          // compute time, subtract cost of running loop         // cost of running loop.          double averagetime = ((midpointtime - starttime) - (stoptime - midpointtime))                 / timestoloop;          system.out.println(averagetime);     }   } 

first off, not measuring complexity in code. doing measuring (or attempting measure) performance. when graph numbers (assuming correctly measured) performance curve particular use-case on finite range of values scaling variable.

that not same computational complexity measure; i.e. big o, or related bachman-landau notations. these mathematical limits scaling variable tends infinity.

and not nitpick. quite easy construct examples performance characteristics change markedly n gets large.

what doing when graph performance on range of values , fit curve estimate complexity.

---

the second point that complexity of arraylist.remove(index) sensitive value of index list length.

• the "advertised" complexity of o(n) average , worst cases.

• in best case, complexity o(1). really!

  this happens when remove last element of list; i.e. index == list.size() - 1. can performed 0 copying; @ code @paxdiablo included in answer.

---

now question. there number of reasons why code give incorrect measurements. example:

• you not taking account of jit compilation overheads , other jvm warmup effects.

• i can see places jit compiler potentially optimize away entire loops.

• the way measuring time strange. try treating algebra ... , simplifying.

          ((midpoint - start) - (stop - midpoint)) / count; 

  the midpoint term disappears ....

• you removing half of elements list, measuring on range 50,000 100,000 of scaling variable. (and expect plotting against scaling variable; i.e. plotting f(n + 5000) against n.

• the time intervals measuring could be small clock resolution on machine. (read javadocs nanotime() see resolution guarantees.)