GATE CS 1999 Q1.16 — Asymptotic Worst Case Time and Space Complexity

We can compute $a^n$ efficiently using the repeated squaring method (also known as exponentiation by squaring).

Let $n = 2^k$ for some non-negative integer $k$. We can compute the powers of $a$ sequentially as follows:

• $a^2 = a \cdot a$   (1 multiplication)
• $a^4 = (a^2)^2$   (2 multiplications)
• $a^8 = (a^4)^2$   (3 multiplications)
• $\dots$
• $a^{2^k} = (a^{2^{k-1}})^2$   ($k$ multiplications)

Since $n = 2^k$, taking the logarithm on both sides gives:

Thus, the minimum number of multiplications required to compute $a^n$ when $n$ is a power of $2$ is $\log_2 n$.

Correct Option: A