how can i prove the following algorithm?

Question

Exp(n)
  if n == 1
    return 2

  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 or Power(2, n)

Answer 1

To compute $\exp(1)$ it does $0$ multiplications, since it enters the if and returns 2.

Assume that, for all $k<n$, to compute $\exp(k)$ it does no more than $2\log_2(k)$ multiplications.

To compute $\exp(n)$ we have two cases. Either $n$ is even and the number of multiplication is $1$ more than the number done for $\exp(n/2)$, or $n$ is odd and the number of multiplications is $2$ more than the number of multiplications done for $\exp((n-1)/2)$.

In the first case we have that the number of multiplications is no more than $2\log_2(n/2)+1=2\log_2(n)-2+1\leq 2\log_2(n)$. In the second case the number of multiplications is no more than $2\log_2((n-1)/2)+2=2\log_2(n-1)\leq 2\log_2(n)$.

Therefore, the number of multiplications to compute $\exp(n)$ is no more than $2\log_2(n)$.

By induction, this holds for all positive integers $n$.