Skip to content
GATETECH
Official PYQ · 2014Set 1 · Q42Asymptotic Worst Case Time and Space ComplexityMCQ1 mark

GATE CS 2014 Set 1 Q42 — Asymptotic Worst Case Time and Space Complexity

Explain with AI

Consider the following pseudo code. What is the total number of multiplications to be performed?

D = 2    
for i = 1 to n do
    for j = i to n do
        for k = j + 1 to n do
            D = D * 3
Choose one option
View worked solution

Answer: C

To find the total number of multiplications performed, we need to count the number of times the innermost statement D = D * 3 is executed. This is equivalent to finding the number of triples (i,j,k)(i, j, k) that satisfy the loop conditions:

1≤i≤j<k≤n1 \le i \le j < k \le n

We can transform this inequality to make all relations strictly less than (<<):

  • Let j′=j+1j' = j + 1. Since i≤ji \le j, we have i<j+1  ⟹  i<j′i < j + 1 \implies i < j'.
  • Since j<kj < k, we have j+1≤k  ⟹  j′≤kj + 1 \le k \implies j' \le k.
  • Let k′=k+1k' = k + 1. Since j′≤kj' \le k, we have j′<k+1  ⟹  j′<k′j' < k + 1 \implies j' < k'.

Substituting these, the condition becomes:

1≤i<j′<k′≤n+11 \le i < j' < k' \le n + 1

This is equivalent to choosing 33 distinct integers {i,j′,k′}\{i, j', k'\} from the set {1,2,…,n+1}\{1, 2, \dots, n+1\}. The number of ways to do this is:

(n+13)=(n−1)n(n+1)6\binom{n+1}{3} = \frac{(n-1)n(n+1)}{6}

Here, (n−1)(n-1), nn, and (n+1)(n+1) are three consecutive integers. Thus, the total number of multiplications is one-sixth of the product of 33 consecutive integers.

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

Published
Report a correction
Keep exploringMore Asymptotic Worst Case Time and Space Complexity questions