When we analyzed the Towers of Hanoi algorithm, we counted the number of moves of individual...

Transcribed Image Text:

When we analyzed the Towers of Hanoi algorithm, we counted the number of moves of individual rings, implicitly assuming that this operation takes constant time. Suppose instead that the time it takes to move a single ring is equal to the size of the ring, meaning that the th-smallest ring takes i steps to move, for each 1in. Write the resulting recurrence for the running time of the algorithm, and solve that recurrence. (15 points) You can utilize the following identity in your analysis without giving a proof: K sum112 (K-1)2+1 +2. = When we analyzed the Towers of Hanoi algorithm, we counted the number of moves of individual rings, implicitly assuming that this operation takes constant time. Suppose instead that the time it takes to move a single ring is equal to the size of the ring, meaning that the th-smallest ring takes i steps to move, for each 1in. Write the resulting recurrence for the running time of the algorithm, and solve that recurrence. (15 points) You can utilize the following identity in your analysis without giving a proof: K sum112 (K-1)2+1 +2. =