# how can i prove the following algorithm?

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)

To compute $$\exp(1)$$ it does $$0$$ multiplications, since it enters the if and returns 2.
Assume that, for all $$k, 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$$.