A.

Consider a version of table expansion where we increase the size of the table by a factor of 10 whenever the table is full. (For instance, a table with size 10 is expanded to size 100. A table with size 100 is expanded to size 1000.) Each insertion without table expansion takes (1) time. Table expansion takes ck time where k is the number of elements in the new table. Initially, the table has size 10. Prove that n insertions into an empty table take a total of (n) time (an average of (1) time per insertion.)

B.

Consider a version of table deletion where we replace the table of size s with a table of size (s - 1000) whenever the table has 1000 or more empty locations. Each deletion which does not change the table size takes (1) time. Resizing the table takes cs time where s is the size of the table being replace. Analyze the TOTAL time to delete n elements from a table of size n. Explain your answer.

O