The GATE Grind

GATE 2014 CS (CS1) – Question 52

Algorithms · Asymptotic Analysis and Time/Space Complexity · 2 marks · Multiple choice

Find the total multiplications in this pseudocode (inclusive loop bounds):

D = 2
for i = 1 to n
for j = i to n
for k = j + 1 to n
D = D * 3

  1. Half the product of three consecutive integers
  2. One-third the product of three consecutive integers
  3. One-sixth the product of three consecutive integers
  4. None of the above

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) One-sixth the product of three consecutive integers

Explanation

For each j, there are j possible i values and n−j possible k values. The count isΣj(n−j)=nΣj−Σj²=n(n+1)(n−1)/6. This is **one-sixth the product of three consecutive integers,C**. Only the innermost assignment multiplies.