Consider a smart array that automatically expands on demand. (Like the java.util
ID: 3668208 • Letter: C
Question
Consider a smart array that automatically expands on demand. (Like the java.util.ArrayList.) It starts with some given initial capacity of 100, and whenever it expands, it adds 50 to the current capacity. So, for example, at the 101st add, it expands to a capacity of 150. How many total units of work would be needed to add 1000 items to this smart array? Assume it takes one unit of work to write an item into an array location, and one unit of work to allocate a new array. Could someone explain how the units of work are calculated.
Explanation / Answer
How many total units of work would be needed to add 1000 items to this smart array?
=> work done to add 1000 items = 1000 unit;
=> Number of times we need to allocate a new Array = (1000 - 100)/50 = 18
(100 to 150 on adding of 101th element);
(150 to 200 on adding of 151th element);
.
.
.
(950 to 1000 on adding of 951th element);
=> 1 for initial allocation of an array of 100 size;
Total work done is
=> 1000 + (1000 - 100)/50 + 1
=> 1000 + 18 + 1
=> 1019