how can i prove the following algorithm?

Question

Exp(n)
  If n = 0
    Return 1
  End If
  
  If n%2==0
    temp = Exp(n/2)
    Return temp × temp
  Else //n is odd
    temp = Exp((n−1)/2)
    Return temp × temp × 2
  End if

how can i prove by strong induction in n that for all n ≥ 1, the number of multiplications made by Exp (n) is ≤ 2 log2 n.

ps: Exp(n) = 2^n

Answer 1

A simple way is to use strong induction.

• First, prove that Exp(0) terminates and returns 2^0.

• Let N be some arbitrary even nonnegative number.

• Assume the function Exp correctly calculates and returns 2^n for every n in [0, N].

• Under this assumption, prove that Exp(N+1) and Exp(N+2) both terminate and correctly return 2^(N+1) and 2^(N+2).

You're done! By induction it follows that for any nonnegative N, Exp(N) correctly returns 2^N.

PS: Note that in this post, 2^N means "two to the power of N" and not "bitwise xor of the binary representations of 2 and N".

Answer 2

The program exactly applies the following recurrence:

P[0] = 1
n even -> P[n] -> P[n/2]²
n odd  -> P[n] -> P[(n-1)/2]².2

1. the program always terminates, because for n>0, n/2 and (n-1)/2 < n and the argument of the recursive calls always decreases.

2. P[n] = 2^n is the solution of the recurrence. Indeed,

• n = 0 -> 2^0 = 1
• n = 2m -> 2^n = (2^m)²
• n = 2m+1 -> 2^n = 2.(2^n)²

and this covers all cases.

As every call decreases the number of significant bits of n by one and performs one or two multiplications, the total number does not exceed two times the number of significant bits.