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

Back to Assignment Page
Back to Assignment 1