Clever Geek Handbook

Big-O runtime to add N elements to ArrayList

Let's say I add N items to ArrayList

in Java. What's a bad time for this? I know O (N) can add one element because the array may need to be resized. It won't resize N times when I add N elements or even a factor of N, because (AFAIK) it ArrayList

grows in size by a certain factor every time I resize. This will mean a number of changes in the log (N). So it looks like O (N log (N)) should be inserting N elements, but I'm not entirely sure about that. An old computer science exam I am looking at had the answer as O (N ^ 2). Did I miss something?

int newCapacity = (oldCapacity * 3)/2 + 1;

( from this answer )

+3


source to share


1 answer


Dynamic array is well studied in computer science in depreciation analysis. The short answer is that when running from an empty dynamic array and adding N elements, the total time is O (N).

You are correct that adding a single item has the worst O (N) time to resize, and that O (log N) sizes do occur.



But when we add these resize operations, the total is only O (N), which is very good. Here is an example to illustrate when the scale factor is 2 (instead of the scale factor of ArrayList 3/2):

N = 64: resize to 1, 2, 4, 8, 16, 32, 64. Total operations = 127 (roughly 2 N ).

+5


source






More articles:


All Articles