144 Suppose array capacity grows by 50 every time a dynamic

144. Suppose array capacity grows by 50 every time a dynamic array fills. If the only events are insertions, the growing events:

(A) occur less and less frequently (B) cannot be characterized in terms of frequency (C) occur more and more frequently (D) occur periodically

145. Suppose array capacity doubles every time a dynamic array fills, If the only events are insertions, the average cost of an insertion, in the limit, is:

(A) the log of the capacity (B) constant (C) linear (D) the log of the size 21

146. Suppose array capacity grows by 10 every time a dynamic array fills, If the only events are insertions, the average cost of an insertion, in the limit, is:

(A) quadratic (B) constant (C) the log of the size (D) linear (E) the log of the capacity

147. Suppose array capacity grows by 10 every time a dynamic array fills, If the only events are insertions, the growing events:

(A) occur less and less frequently (B) occur periodically (C) cannot be characterized in terms of frequency (D) occur more and more frequently

148. If array capacity grows by 10 every time a dynamic array fills, the average cost of an insertion in the limit is:

(A) linear (B) the log of the capacity (C) the log of the size (D) constan

Solution

144. (D) occur periodically. This is because the array size is increased by 50 and this will happen only after the existing size is filled up.

145. (B) The cost of insertion in dynamic arrays is always considered to be constant. Since only insertion happens and no deletion happens, the answer would be constant.

146. (B) Again , cost for array insertion is constant.

147. (D) occur more and more frequently. For every 10 array insertions, the array size needs to be increased by 10 again.

148. (D) Again, the cost of array insertions is constant.