25-05-2012, 01:34 PM
Amortized Analysis
amortized(1).pdf (Size: 182.91 KB / Downloads: 99)
Incrementing a Binary Counter
It is a straightforward exercise in induction, which often appears on Homework 0, to prove that any
non-negative integer n can be represented as the sum of distinct powers of 2. Although some students
correctly use induction on the number of bits—pulling off either the least significant bit or the most
significant bit in the binary representation and letting the Recursion Fairy convert the remainder—the
most commonly submitted proof uses induction on the value of the integer, as follows:
Proof: The base case n = 0 is trivial. For any n > 0, the inductive hypothesis implies that there is set of
distinct powers of 2 whose sum is n