3. Uoft bookstore sells books. At the bookstore, UofT displays the number of books that are...

Transcribed Image Text:

3. Uoft bookstore sells books. At the bookstore, UofT displays the number of books that are in store. Every time a book enters the store, a worker will update the display of the current number of books. This update costs UofT a + bk dollars for k digit changes, where a, b are positive real numbers. For example, if a book enters as the 2000-th book, then the cost of changing the display is a + 4b (1999 to 2000 differs in 4 digits). Denote Insert() as the event of a new book coming to UofT bookstore. Using the potential method, prove that the amortized cost for the Insert() is a + dollars. We assume books cannot be removed from the store, and imagine that there are infinite zeroes at the left of the number, so 999 to 1000 changes 4 digits. 106 9 (Hint: The more nines in the end, the more expensive the update cost) 3. Uoft bookstore sells books. At the bookstore, UofT displays the number of books that are in store. Every time a book enters the store, a worker will update the display of the current number of books. This update costs UofT a + bk dollars for k digit changes, where a, b are positive real numbers. For example, if a book enters as the 2000-th book, then the cost of changing the display is a + 4b (1999 to 2000 differs in 4 digits). Denote Insert() as the event of a new book coming to UofT bookstore. Using the potential method, prove that the amortized cost for the Insert() is a + dollars. We assume books cannot be removed from the store, and imagine that there are infinite zeroes at the left of the number, so 999 to 1000 changes 4 digits. 106 9 (Hint: The more nines in the end, the more expensive the update cost)