Official PYQ · 2015Set 3 · Q49Asymptotic Worst Case Time and Space ComplexityNAT1 mark

GATE CS 2015 Set 3 Q49 — Asymptotic Worst Case Time and Space Complexity

Suppose $c = \langle c[0], \dots, c[k-1]\rangle$ is an array of length $k$ , where all the entries are from the set $\{0, 1\}$ . For any positive integers $a \text{ and } n$ , consider the following pseudocode.

DOSOMETHING (c, a, n)

z ← 1
for i ← 0 to k-1
     do z ← z² mod n
     if c[i]=1
           then z ← (z × a) mod n
return z

If $k=4, c = \langle 1, 0, 1, 1 \rangle , a = 2, \text{ and } n=8$ , then the output of DOSOMETHING(c, a, n) is _______.

View worked solution

Answer: 0

We can trace the execution of the algorithm step-by-step with the initial value $z = 1$ , $a = 2$ , and $n = 8$ :

Iteration $i = 0$ ( $c[0] = 1$ ):
First, $z \leftarrow z^2 \pmod 8 \implies 1^2 \pmod 8 = 1$ .
Since $c[0] = 1$ , $z \leftarrow (z \times a) \pmod 8 \implies (1 \times 2) \pmod 8 = 2$ .
Iteration $i = 1$ ( $c[1] = 0$ ):
First, $z \leftarrow z^2 \pmod 8 \implies 2^2 \pmod 8 = 4$ .
Since $c[1] = 0$ , the condition is false, so $z$ remains $4$ .
Iteration $i = 2$ ( $c[2] = 1$ ):
First, $z \leftarrow z^2 \pmod 8 \implies 4^2 \pmod 8 = 16 \pmod 8 = 0$ .
Since $c[2] = 1$ , $z \leftarrow (z \times a) \pmod 8 \implies (0 \times 2) \pmod 8 = 0$ .
Iteration $i = 3$ ( $c[3] = 1$ ):
First, $z \leftarrow z^2 \pmod 8 \implies 0^2 \pmod 8 = 0$ .
Since $c[3] = 1$ , $z \leftarrow (z \times a) \pmod 8 \implies (0 \times 2) \pmod 8 = 0$ .

At the end of the loop, the function returns $z = 0$ .

Free practice · Your answers on this page are not saved.

Published 10 Oct 2026

Report a correction

Browse this topic

More Asymptotic Worst Case Time and Space Complexity questions

GATE CS 2015 Set 3 Q49 — Asymptotic Worst Case Time and Space Complexity

Related questions