Assume that n is a positive integer. For each of the following algorithm segment

Question

Assume that n is a positive integer. For each of the following algorithm segments, how many times will the innermost loop be iterated when the algorithm segment is implemented and run?

1)
for k := 1 to n
for j := 1 to k
    [Statements in the body of the inner loop, none         containing branching statements that lead outside the loop]
   next j
next k

2)
for k := 1 to n - 1
for j := 1 to k + 1
     [Statements in the body of the inner loop, none containing branching statements that lead outside the loop]
   next j
next k

3)
for k := 1 to n - 1
    for j := k+1 to n
       [Statements in the body of the inner loop, none containing branching statements that lead outside the loop]
    next j
next k

4)
for k := 1 to n - 1
    for j := k to n
       [Statements in the body of the inner loop, none containing branching statements that lead outside the loop]
    next j
next k

5)
for k := 1 to n
   for j := 1 to k
      for i := 1 to j
         [Statements in the body of the inner loop, none containing branching statements that lead outside the loop]
      next i
   next j
next k

6)
for k := 1 to n
   for j := 1 to k - 1
      for i := 1 to j - 1
        [Statements in the body of the inner loop, none containing branching statements that lead outside the loop]
      next i
   next j
next k

Explanation / Answer

Things to know before going to the answer:

if there are two loops in a nested fashion in a program.Think that the outer loop (i) runs 1 to 5 times and the inner one runs 1 to i

then for i=1 inner loop runs 1 time

for i=2 inner loop runs 2 times

for i=3 inner loop runs 3 times

for i=4 inner loop runs 4 times

and for i=5 inner loop runs 5 times

total number of times inner loop was run=1+2+3+4+5=15

replace the 5 with an unknown number then the inner loop will run till=1+2+3+4+5+............+n

In mathematics, we have a formula for the sum of natural numbers that is n*(n+1) whole divided by 2.

let try with n=5

5*6=30 divided by 2 =15 which is equal to our manual calculation

1) The loop runs n(n+1)/2 times

the condition mentioned in the first loop is same as explained in the example before answers

2) The loop runs same as loop1 which runs n(n+1)/2 times

Here in this loop compared to the first loop n is reduced by one and k is increased by 1. Which gives the same result as n*(n+1)/2

3)The third one runs (n-1)n/2 times

Here if i=1 we are running the inner loop from 2 to n

and if i=2 we are running the inner loop from 3 to n so we are reducing the n value by 1 so substitute n-1 in our natural number sum formula

((n-1)(n-1+1)) / 2 which is equal to ((n-1)*n)/2

4)This loop runs (n(n+1)/2)-1 times

Here no need to submit the (n-1) number as the previous loop because we running the inner loop from k to n

But the outer loop was running till n-1 only.

Please see the first n=5 example same one here comes like 5+4+3+2=14 because we are running k to n each time.the last loop where n=5 will not run.

so we have to reduce 1 from our natural number formula ((n*(n+1))/2 )-1

5)This loop runs n(n+1)(n+2)/6 times

This is a standard formula to calculate the number of times a nested loop runs.

formula is n(n+1)(n+2).......(n+r) whole divided by r!

where r is the number of loops here r is 3

So, n(n+1)(n+2)/6

But careful using the formula the break conditions should be same

6)This loop runs n*(n-1)(n-2)/6 times

in this loop, we are running inner loops till k-1 and j-1 so we have to substitute n-1 value in the formula mentioned above

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects