The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+14 votes

If $n$ is a power of $2$, then the minimum number of multiplications needed to compute $a^n$ is

  1. $\log_2 n$
  2. $\sqrt n$
  3. $n-1$
  4. $n$
in Algorithms by Veteran (52.1k points)
edited by | 1.6k views

2 Answers

+26 votes
Best answer
a. $\log n$

$a^n = (a^2)^{\frac{n}{2}}$.

One multiplication and recurrence on $\frac{n}{2}$. So, we get the recurrence relation for the number of multiplications as

$T(n) = T(n/2) + 1$.

This gives $T(n) = \log_2 n$

For n = 8, we can do

$b = a \times a$

$b = b\times b$

$b = b\times b$ and we get $b = a^8$
by Veteran (416k points)
edited by
Using Recurrence:

$a^n = a^{\frac{n}{2}}.a^{\frac{n}{2}}$
(here n is in a power of 2, so we would never have a fraction, each time when we divide n with 2.)

Here once we solve $a^{\frac{n}{2}}$, then we need one more multiplication that is multiplying $a^{\frac{n}{2}}$ to itself.

Hence recurrence:
T(n) = T$(\frac{n}{2})$+1.
Option 1 satisfies this.

n is a power of 2 .

So, $a_{n}$ could be $\left (2^{x} \right )^{n}$

Now, if we think $\left (2^{x} \right )^{n}$=$2^{m}$


$T\left ( 2^{m} \right )=T\left (2 ^{\frac{m}{2}} \right )+1$

Now, applying master 2nd theorem , answer is Option (A)


@Sachin Mittal 1 Sir if the question had "If n is a power of 3" then will the recurrence relation be:

T(n)= T(n/3) + 2 ?

+5 votes
let n = 2^k

a^n = a^(2^k) = (a^2)^k

total multiplications = k-1 + 1(for a^2) = k = logn
by (437 points)
Suppose a=2 k=3 ... So $2^{(2^{3})}$ = $2^{8}$ = 256

 and  $(2^{2})^{3}$ = $4^{3}$ = 64 .... is it ok according to ur a^(2^k) = (a^2)^k ??

a^(2^k) = (a^2)^k

It is wrong.

For k=3,

a^(2^k) = a^(2^3) = a^8


(a^2)^k = (a^2)^3 = a^6


Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,830 questions
54,811 answers
80,894 users