edited by
35,414 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

Best answer
104 votes
104 votes

Total number of multiplications

$= \displaystyle \sum_{i=1}^{n}\sum_{j=i}^{n}\sum_{k=j+1}^{n} 1$
$= \displaystyle\sum_{i=1}^{n}\sum_{j=i}^{n}(n-j)$
$=\displaystyle \sum_{i=1}^{n}(n-i) + (n-(i+1)) + \ldots+ (n-n)$
$\displaystyle =\frac{1}{2}\sum_{i=1}^{n}(n-i)(n-i+1)$
$\displaystyle =\frac{1}{2}\sum_{i=1}^{n}(n^{2} +n+i^{2}-(2n+1)i)$
$\displaystyle = \frac{1}{2} \left( n^3 + n^2 + \sum_{i=1}^{n}i^2 - (2n+1). \sum_{i=1}^{n} i \right)$
$\displaystyle=    \frac{1}{2} \left( n^3 + n^2 + \frac{n. (n+1). (2n+1)}{6} - (2n+1). \frac{n. (n+1)}{2} \right)$
$ \displaystyle = \frac{1}{2} \left( n^3 + n^2  - \frac{n. (n+1). (2n+1)}{3} \right)$
$\displaystyle =  \frac{n}{6} \left( 3n(n+1)   -  (n+1). (2n+1) \right)$
$ \displaystyle= \frac{n. (n+1)}{6} (n-1)$
$ \displaystyle =\frac{(n-1)n(n+1)}{6}$

Therefore, correct answer would be (C).

edited by
40 votes
40 votes

 

Same as Best answer, but I Cleared some Basic steps more.

edited by
26 votes
26 votes

i goes 1 to n

j goes i to n

k goes j+1 to n


let's take first iteration for i: as i=1

j goes 1 to n

for j=1 , k: 2 to n = (n-1) times
    j=2 , k: 3 to n = (n-2) times
    ...
  j=n-1 , k: n to n = 1 time
  j= n  , k: 0 times


so, for i=1,
 number of multiplications : 1 + 2 + ... + (n-1)

similarly for i = 2,
 1+2+ .... + (n-2)

and so on,

for i = (n-1)
   1

for i = n
  0

so, for every i say last term as T

we have for every i, 1+2+3+... + T = T(T+1)/2 = (T^2  + T)/2

where T goes from 1 to (n-1)

∑  (T^2  + T)/2 , T goes 1 to (n-1) = (n-1)(n)(n+1)/ 6

so, option C is correct

19 votes
19 votes
C

Take a simple example with n=3

It will give 4multiplications. For verification take other example with n=4.

Only choice which satisfy is c
Answer:

Related questions

12.9k
views
5 answers
49 votes
go_editor asked Sep 28, 2014
12,919 views
Consider the following C function in which size is the number of elements in the array E: int MyX(int *E, unsigned int size) { int Y = 0; int Z; int i, j ... in all possible sub-arrays of array E.the sum of all the elements in the array E.
55.1k
views
16 answers
89 votes
go_editor asked Sep 28, 2014
55,057 views
The minimum number of comparisons required to find the minimum and the maximum of $100$ numbers is ________
9.8k
views
9 answers
47 votes
go_editor asked Sep 28, 2014
9,840 views
There are $5$ bags labeled $1$ to $5$. All the coins in a given bag have the same weight. Some bags have coins of weight $10$ gm, others have coins of weight ... $11$ gm coins is ___.
12.4k
views
4 answers
34 votes
go_editor asked Sep 26, 2014
12,418 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 adjacency matrix?$\Theta(n)$\Theta(n+m)$\Theta(n^2)$\Theta(m^2)$