Question about the Amortized Analysis

Amortized Analysis a. In class, we discussed implementing a binary heap as an array. When the heap fills, assume you double the size of the array and copy the elements into the new array. Assume that copying n elements is O(n). Starting with an initial array size of 1, what is the amortized cost of inserting M elements into your heap? Note, the costs for a fixed array implementation are well described in your book b. Assume you have a hash function family that magically does not collide until the load factor on your array implementation reaches 50%, even though your table size is always a power of 2. Every time you resize your table, you must rehash each element. What is the amortized cost of insertions? Using the binary counter example from the slides, what is the amortized cost of increments if the cost to flip the k-th bit (0000 to 0001 flips bit 1) is k? Using the binary counter example from the slides, what is the amortized cost of increments if the cost to flip the k-th bit (0000 to 0001 flips bit 1) is 2k? Using the binary counter example from the slides, what is the amortized cost of increments if the cost to flip the k-th bit (0000 to 0001 flips bit 1) is k2? c. d. e. Amortized Analysis a. In class, we discussed implementing a binary heap as an array. When the heap fills, assume you double the size of the array and copy the elements into the new array. Assume that copying n elements is O(n). Starting with an initial array size of 1, what is the amortized cost of inserting M elements into your heap? Note, the costs for a fixed array implementation are well described in your book b. Assume you have a hash function family that magically does not collide until the load factor on your array implementation reaches 50%, even though your table size is always a power of 2. Every time you resize your table, you must rehash each element. What is the amortized cost of insertions? Using the binary counter example from the slides, what is the amortized cost of increments if the cost to flip the k-th bit (0000 to 0001 flips bit 1) is k? Using the binary counter example from the slides, what is the amortized cost of increments if the cost to flip the k-th bit (0000 to 0001 flips bit 1) is 2k? Using the binary counter example from the slides, what is the amortized cost of increments if the cost to flip the k-th bit (0000 to 0001 flips bit 1) is k2? c. d. e