0
$\begingroup$
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)

$\endgroup$

1 Answer 1

1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.