COMP4500/7500 Advanced Algorithms & Data Structures Tutorial Exercises 8 (2014/2)∗
School of Information Technology and Electrical Engineering, University of Queensland
September 12, 2014
This material aims to familiarise you with amortised analysis. A good treatment of this may be found in CLRS Chapter 17; CLR Chapter 18.
1. (Kingston exercise 3.6)
Consider the following algorithm for adding one to a binary number, represented as an array, A, of k bits, assuming that there is no overflow. The indices of A range from 0 to k − 1. The number I represented by the array is given by the formula
INCREMENT(A, k)
1 2 3 4 5 6
i=0 whilei