If n is a power of 2, then the minimum number of multiplications needed to…
1999
If n is a power of 2, then the minimum number of multiplications needed to compute aⁿ is:
- A.
log₂ n
- B.
√n
- C.
n - 1
- D.
n
Attempted by 98 students.
Show answer & explanation
Correct answer: A
The correct answer is: log₂ n.
Let n = 2ᵏ. To compute aⁿ efficiently, use repeated squaring. First compute a² using one multiplication, then square again to get a⁴, then a⁸, and so on.
After k squaring multiplications, the exponent becomes 2ᵏ, which is n. Therefore the number of multiplications required is k = log₂ n.
The other choices are not correct because the count is based on how many times the exponent must be doubled from 1 to n, not on √n, n - 1, or n.