GATE CS 2020 Q48 — Asymptotic Worst Case Time and Space Complexity

The function pp(a, b) implements the standard binary exponentiation (or exponentiation by squaring) algorithm to compute $a^b$. Let us trace the execution for pp(3, 4) step-by-step.

Step 1: Trace of tob(4, arr)

The function tob(b, arr) converts the integer $b$ into its binary representation and stores the bits in arr in least-significant-bit (LSB) first order. It returns the number of bits (length).

For $b = 4$:

• Iteration 1 ($i = 0$): $b = 4$. Since $4 \% 2 == 0$, arr[0] = 0. Then $b = 4/2 = 2$.
• Iteration 2 ($i = 1$): $b = 2$. Since $2 \% 2 == 0$, arr[1] = 0. Then $b = 2/2 = 1$.
• Iteration 3 ($i = 2$): $b = 1$. Since $1 \% 2 == 1$, arr[2] = 1. Then $b = 1/2 = 0$.

The loop terminates because $b = 0$. The function returns i = 3. Thus, len = 3 and arr = {0, 0, 1}.

Step 2: Trace of pp(3, 4)

We initialize ex = a = 3, tot = 1, and len = 3. The loop runs for $i = 0, 1, 2$:

After the loop finishes, the function returns tot, which is 81.

Note: This is equivalent to calculating $3^4 = 81$.