edited by
34,046 views
80 votes
80 votes

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 
  1. Half of the product of the $3$ consecutive integers.
  2. One-third of the product of the $3$ consecutive integers.
  3. One-sixth of the product of the $3$ consecutive integers.
  4. None of the above.
edited by

12 Answers

0 votes
0 votes

The total number of multiplications to be performed will be equal to the number of times the inner-most loop executes , ie , the loop with 'k' as the counter variable.

When i=1, j=1, then the 'k' loop executes (n-1) times
i=1 , j=2 , => (n-2) times
....
=> for i=1 , the no of multiplications is = (n-1) + (n-2) + .... + 2 + 1 = ∑(n-1)

for i=2 , similarly , the no of multiplications = ∑(n-2)

...

for i=n-1 , the no of multiplications = ∑1 = 1

Hence , the total no of multiplications is = ∑(n-1) + ∑(n-2) + .... + ∑(2) + ∑(1)

=(1+2+... +n-1) + (1+2+...+n-2) + .... + (2+1) + (1)
=Sn-1 + Sn-2 + ... + S2 + S1
=∑Si (from i=1 to n-1)
=∑[n*(n-1)/2]
=∑[(n2)/2] - ∑[(n)/2]
= (n)(n+1)(2n+1)12−n(n+1)4=(n−1)(n)(n+1)6

ANSWER : (C) One-sixth of the product of the 3 consecutive integers.

Source:http://www.techtud.com/example/consider-following-pseudo-code-gate-2014

0 votes
0 votes
Take n and observe how many times the loop executes the statement D=D*3

 

for n=2: 1 times (1*2*3)/6

for n=3 : 4 times (2*3*4)/6

for n=4: 10 times (3*4*5)/6

for n=5: 35 times (5*6*7)/6
0 votes
0 votes

This kind of loops can be thought similar to ball and buckets problem where range of i (1 to n) corresponds to n number of buckets and r number of loop variables corresponds to r balls.

Total no of loop executions are$\large _{}^{n+r-1}\textrm{C}_{r}$ .(Check from Rosen page no 427 for more explanation)

Now in this question, total number of loop executions = $\large _{}^{n+3-1}\textrm{C}_{3}$

but we have counted extra executions cause k = j+1 to n not j to n , So we have to subtract those cases which is $\large _{}^{n+2-1}\textrm{C}_{2}$ (cause we have to subtract those cases where i <= j = k so j,k can be thought as one variable)

So total number of multiplications to be performed = $\large _{}^{n+2}\textrm{C}_{3}$ – $\large _{}^{n+1}\textrm{C}_{2}$ = $\large \frac{(n+1).n.(n-1)}{6}$

Answer:

Related questions

89 votes
89 votes
16 answers
2
go_editor asked Sep 28, 2014
53,592 views
The minimum number of comparisons required to find the minimum and the maximum of $100$ numbers is ________
34 votes
34 votes
4 answers
4
go_editor asked Sep 26, 2014
12,111 views
Let $G$ be a graph with $n$ vertices and $m$ edges. What is the tightest upper bound on the running time of Depth First Search on $G$, when $G$ is represented as an adjac...