Amortized Cost Is Not Average Case Time. Do not confuse amor-

tized cost with that of average case time. In average case analysis, the evaluation is done by computing an average over all possible inputs and sometimes requires the use of statistics. Amortized analysis computes an average cost over a sequence of operations in which many of those opera- tions are cheap and relatively few are expensive in terms of contributing to the overall time.

Consider Table 4.5 on numbered page 112 in your textbook. Write the Python functions described below: amortized_cost( i ) returns the costs Si, ei, and size values for a given i value, where i 2 1. generate_table( n ) should print out a table such as Table 4.5 for any given n. For example, Table 4.5 would be for n = 16, the number of items to be appended to a list. . - # Write your code here # You may use multiple code cells like this # def amortized_cost( i ): IIIIII Provide docstring here IIIIII pass def generate_table( n ): IIIIII Provide docstring here pass i Si li Size Note that n must be a 1 1 - 1 2 1 1 2 3 1 2 4 4 1 4 5 1 8 6 1 8 7 1 8 8 1 8 List Contents 1 To append 16 items to an initially empty 1 power of 2 in order for array, we need 16 storage cost (s_i) and the (2n - 1) relationship 15 expansion cost (e_i) as you can tell from 1 2 to hold. the totals at the bottom of this table. 1 2 3 Similarly, to append 32 items--twice as many as what this table demonstrates, we 1 2 3 would have to pay 32 storage cost (s_i) and 31 expansion cost le_i), since we would have 1 2 3 4 5 to expand the given array by another 16 cells 1 2 3 4 5 6 at the 17th append operation. However, until and including the 32nd append operation, we 1 2 3 4 5 6 7 would only have to pay one storage cost (s_i) for every append operation and no expansion 1 2 3 4 5 6 7 | 8 cost le_i) at all. This means that the total cost would be 63, 1 2 3 4 5 6 7 8 9 which (2n - 1), as 1 2 3 4 5 6 7 8 9 10 before where n is the numer of items 1 2 3 4 5 6 7 8 9 10 11 appended. In other words, we would 1 2 3 4 5 6 7 8 9 10 11 12 pay another 16 s_j 1 2 3 4 5 6 7 8 9 10 11 12 13 and 16 e_i on top of the existing 1 2 3 4 5 6 7 8 9 10 11 12 13 14 costs shown in this table on top of the 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 total 31 cost. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 CO 8 16 10 1 16 11 1 16 12 1 - 16 13 1 16 14 1 16 15 1 16 16 1 16