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

13 votes
13 votes
i j Inner Loop Iternations
1 1 n-1
1 2 n-2
1 .. ..
1 .. ..
1 n 0
i j Inner Loop Iterations
2 2 n-2
2 3 n-3
2 .. ..
2 .. ..
2 n 0
i j Inner Loop Iterations
n-1 n-1 1
n-1 n 0
i j Inner Loop Iternations
n n 0

Total Number of Inner Loop iterations = (0) + (0+1) + (0+1+2) + (0+1+2+3) +............+ (0+1+2+3+....n-1)

= ∑i=0 to n-1   (0+1+2+.....i)  

= ∑i=0 to n-1   (i*(i+1))/2

= ∑i=0 to n-1   (i+ i)/2

= [ (n-1)(n)(2n-1)/6 + (n-1)n/2 ] / 2

= (n-1)n(n+1)/6

Hence C option is the correct answer. 

4 votes
4 votes

Option C

When difference of the terms of the series form an A.P., then how to write any random term for that series ?

Source :  https://math.stackexchange.com/questions/1961952/how-do-i-find-the-sum-of-a-sequence-whose-common-difference-is-in-arithmetic-pro

Note : There are n-1 terms in the series, I took n terms for easier calculation. It won't affect the answer at all. 

 

 

 

2 votes
2 votes

The statement “D = D * 3” is executed n*(n+1)*(n-1)/6 times. Let us see how.

For i = 1, the multiplication statement is executed (n-1) + (n-2) + .. 2 + 1 times.
For i = 2, the statement is executed (n-2) + (n-3) + .. 2 + 1 times
………………………..
……………………….
For i = n-1, the statement is executed once.
For i = n, the statement is not executed at all

So overall the statement is executed following times
[(n-1) + (n-2) + .. 2 + 1] + [(n-2) + (n-3) + .. 2 + 1] + … + 1 + 0

The above series can be written as
S = [n*(n-1)/2 + (n-1)*(n-2)/2 + ….. + 1]

The sum of above series can be obtained by trick of subtraction the series from standard Series S1 = n2 + (n-1)2 + .. 12. The sum of this standard series is n*(n+1)*(2n+1)/6

S1 – 2S = n + (n-1) + … 1 = n*(n+1)/2
2S = n*(n+1)*(2n+1)/6 – n*(n+1)/2
S = n*(n+1)*(n-1)/6

1 votes
1 votes

 

here i have taken n = 3, unrolled the for loops and then checked the options. Answer is  OPTION D

Answer:

Related questions

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