how can i prove the following algorithm?
To compute $\exp(1)$ it does $0$ multiplications, since it enters the if and returns 2.
Assume that, for all $k&lt;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$.