Problem $1($Extendable arrays$)$

a$)$ We've looked at two ways to grow extendable arrays, with incremental and doubling

approaches. How about a new approach, which does the following, where N is the current

capacity of the array:

when there are N elements and we insert one more, the array is extended by $50\%,$ so

the new capacity is ceil $(1\mathrm{.}5N)$ where ceil is the integer "ceiling" of the number.

Show that with this approach, a sequence of n insert operations, starting from an extendable

array of capacity $N=1,$ takes $O(n)$ time.

b$)$ What can you conclude about the amortized time of the insert operations for the extendable

array in $($a$)?$ Justify your conclusion using definitions.

c$)$ We want to try yet another approach, which does the following, where N is the current

capacity of the array:

when there are N elements and we insert one more, the array is extended by square root

of N cells, so the new capacity is $N+$ceil$(\sqrt[\phantom{2}]{N})$

Show that with this approach, a sequence of n insert operations, starting from an extendable

array of capacity $N=1,$ takes $O(n^{\frac{3}{2}})$ time.

d$)$ What can you conclude about the amortized time of the insert operations for the extendable

array in $($c$)?$ Justify your conclusion.