We consider here just the case that n > 1 is odd.
Let i = (n-1)/2. By the inductive hypothesis, since i < n, the function evalutes log2(i) in not more than 2 lg(i) steps. Since n = 2i+1 we have by the properties of logarithms that lg(n) > lg(2i) = lg(i)+lg(2) = lg(i)+1.
The function evaluates log2(n) by a recursive call to log2(n-1) = log2(2i), followed by a recursive call to log2(i). Thus, by the inductive hypothesis, the function evaluates log2(n) in at most 2lg(i) + 2 < 2lg(n) steps.

Back to Assignment Page
Back to Assignment 1