Consider a smart array that automatically expands on demand. (Like the java.util
ID: 3792407 • Letter: C
Question
Consider a smart array that automatically expands on demand. (Like the java.util.ArrayList.) It starts with an initial capacity of 50, and whenever it expands, it adds 30 to the current capacity. So, for example, at the 51st add, it expands to a capacity of 80.
How many total units of work would be needed to add 300 items to this smart array? (Add appends to the end of the 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 of any length, when expanding. You don't need to count anything else.
Explanation / Answer
Working Procedure:
Array Initial Capacity = 50
Here We knew that, If we add 1 element the capacity of smart array is expanded to 30.
So, 1 unit of work to write an item into smart array.
Therefore 300 items require 300 units of work.
It will need 1 uint of work at one time to expand the array.So far, the smart array need to expand its capacity to hold 300 items.
1 unit of work = 30 capacity of items expanded..
10 units of work = 300 capacity of items expanded (300/30 = 10)
Finally, Total work = write item into location + allocate new array
= 300 + 10
= 310 units of work.