| CSC403: Linear versus Constant Time [1/8] | |
Accessing a linked list element is linear time
Accessing an array list element is constant time
See algs14.PlaygroundIndexing
Output searching for N (will be worst case, since N is at the end of the array or linked list!):
Linked elapsed count N= 512 [ 0.000 : NaN] Linked elapsed count N= 1,024 [ 0.000 : NaN] Linked elapsed count N= 2,048 [ 0.000 : NaN] Linked elapsed count N= 4,096 [ 0.000 : NaN] Linked elapsed count N= 8,192 [ 0.000 : NaN] Linked elapsed count N= 16,384 [ 0.000 : NaN] Linked elapsed count N= 32,768 [ 0.000 : NaN] Linked elapsed count N= 65,536 [ 0.001 : Infinity] Linked elapsed count N= 131,072 [ 0.001 : 1.000] Linked elapsed count N= 262,144 [ 0.002 : 2.000] Linked elapsed count N= 524,288 [ 0.003 : 1.500] Linked elapsed count N= 1,048,576 [ 0.005 : 1.667] Linked elapsed count N= 2,097,152 [ 0.010 : 2.000] Linked elapsed count N= 4,194,304 [ 0.024 : 2.400] Linked elapsed count N= 8,388,608 [ 0.075 : 3.125] Linked elapsed count N= 16,777,216 [ 0.151 : 2.013] Linked elapsed count N= 33,554,432 [ 0.211 : 1.397] Array elapsed count N= 512 [ 0.000 : NaN] Array elapsed count N= 1,024 [ 0.000 : NaN] Array elapsed count N= 2,048 [ 0.000 : NaN] Array elapsed count N= 4,096 [ 0.000 : NaN] Array elapsed count N= 8,192 [ 0.000 : NaN] Array elapsed count N= 16,384 [ 0.000 : NaN] Array elapsed count N= 32,768 [ 0.000 : NaN] Array elapsed count N= 65,536 [ 0.000 : NaN] Array elapsed count N= 131,072 [ 0.000 : NaN] Array elapsed count N= 262,144 [ 0.000 : NaN] Array elapsed count N= 524,288 [ 0.000 : NaN] Array elapsed count N= 1,048,576 [ 0.000 : NaN] Array elapsed count N= 2,097,152 [ 0.000 : NaN] Array elapsed count N= 4,194,304 [ 0.000 : NaN] Array elapsed count N= 8,388,608 [ 0.000 : NaN] Array elapsed count N= 16,777,216 [ 0.000 : NaN] Array elapsed count N= 33,554,432 [ 0.000 : NaN]