Flashcards
Arraylist sizing
Cards in this deck (1)
- 1ArrayList doubles capacity when it is full. Isn't that wasteful?As we insert elements, we double the capacity when the size of the array is a power of 2. 50 after X elements,
we double the capacity at array sizes 1, 2, 4, 8, 16, ... , X.
That doubling takes, respectively, 1, 2, 4, 8, 16, 32,
64, ... , X copies.
What is the sum of 1 + 2 + 4 + 8 + 16 + ... + X? If you read this sum left to right, it starts with 1 and doubles
until it gets to X. If you read right to left, it starts with X and halves until it gets to 1.
What then is the sum of X + X + X + Ys + ... + 1? This is roughly 2X.
Therefore, X insertions take O( 2X) time. The amortized time for each insertion is O( 1)
Information
- Description
- Data Structures (Amortized time) Flashcards on Arraylist sizing, created by Rajaram Mallya on 05/07/2018.
- Created by
- Rajaram Mallya
- Views
- 0
- Rating