Consider table expansion where we increase the size of the table by 75% whenever the table...

Transcribed Image Text:

Consider table expansion where we increase the size of the table by 75% whenever the table is full. (For instance, a table with size 100 is expanded to size 175. A table with size 200 is expanded to size 350.) Each insertion without table expansion takes (1) time. Table expansion takes ck time where k is the size of the new table. Prove that n insertions into an initially empty table of size 2 take a total of O(n) time (an average of (1) time per insertion.) Consider table expansion where we increase the size of the table by 75% whenever the table is full. (For instance, a table with size 100 is expanded to size 175. A table with size 200 is expanded to size 350.) Each insertion without table expansion takes (1) time. Table expansion takes ck time where k is the size of the new table. Prove that n insertions into an initially empty table of size 2 take a total of O(n) time (an average of (1) time per insertion.)