edited by
34,034 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

89 votes
89 votes
16 answers
2
go_editor asked Sep 28, 2014
53,591 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,107 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...