Say I'm adding N items to an ArrayList in Java. What is the worst-case run time for this? I know it can be O(N) to add a single item because the array may have to resize. It won't resize N times as I add N items or even a factor of N because (AFAIK) the ArrayList increases in capacity by some factor each time it resizes. That would mean some kind of log(N) number of resizes. So it seems like it should be O(N log(N)) to insert N items, but I'm not completely sure about this. An old computer science exam I'm looking at had the answer as O(N^2). Am I missing anything?
int newCapacity = (oldCapacity * 3)/2 + 1; (from this answer)
The dynamic array is well-studied in computer science in amortized time analysis. The short answer is that when starting 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-case time of O(N) when a resize must be performed, and that O(log N) resizes take place.
But when we add up these resize operations, the total is only O(N), which is very good. Here's an example to illustrate when the scaling factor is 2 (instead of ArrayList's scaling factor of 3/2):
N = 64: Resize to 1, 2, 4, 8, 16, 32, 64. Total operations = 127 (roughly 2N).
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments