How Many Times Will This Loop Execute

how many times will this loop execute

TL;DR

The loop will be executed for ((total ^ 3) - total) / 6 times and hence that will be the value of sum at the end of the loop.

---

int sum = 0;
for(int i = 0; i < total; i++) { 
    for(int j = i + 1; j < total; j++) {
        for(int k = j; k < total; k++) {
            sum++;    
        }
    }
}

It is easy to see that the outer loop runs for a total times. The second loop is the trickier one

Let's try to work this out

i = 0, j runs from 1..total - 1

i = 1, j runs from 2..total - 1

i = 2, j runs from 3..total - 1

...
i = total - 2, j runs from total - 1 ..total - 1 (will only run once)

i = total - 1, inner loop does not execute as the loop termination condition is true.

The third loop is dependent on the second inner loop - k runs from j..total - 1

Let us take total as 6

j runs from 1..5 -> k runs for 5 times (j = 1) + 4 times(j = 2) + 3 times(j = 3)+ 2 times(j = 4) + 1 time(j = 4)

(Showing a minified version for others)

2..5 -> 4+3+2+1
3..5 3+2+1
4..5 2+1
5..5 1

Which is

1 + 2 + 3 + 4 + 5+
1 + 2 + 3 + 4 + 
1 + 2 + 3 +
1 + 2 +
1

Generally,

1 + 2 + 3 + .. n +
1 + 2 + 3 +..n - 1+
1 + 2 + 3 +..n - 2+
1 + 2 + 3 +
1 + 2 +
1

This boils down to the sum
n * (n - 1)) / 2

For all values of n ranging from 1 to total

This can be verified with the below

int res = 0;
for (int i = 1; i <= total; i++) {
    res += (i * (i - 1))/2;
}

res will be equal to your sum.

Mathematically, the above is

((total ^ 3) - total) / 6

Derivation:

References:

Sums of the First n Natural Numbers

Sum of the Squares of the First n Natural Numbers

How many times will the while loop be executed?

Algorithm for No Carry Adder:

function no_carry_adder(A,B)
    while B != 0:
        X = A XOR B, Bitwise-XOR of A,B.
        Y = A AND B, Bitwise-AND of A,B.
        A = X
        B = Y << 1, Multiplying Y by 2.
    return A

As you can see, the while loop executes those four instructions again and again until B = 0, and when B = 0, binary number stored in A is the answer.
Now the question was to find out how many times the while loop will execute before B = 0 or B becomes zero.

If I have gone for the naive way i.e write the algorithm as it is described in any programming language like it will give me an answer but it will be time-consuming if the number of bits in the binary string A and B is > 500.

How can I make a faster algorithm?
Let's take a look at different cases,

• Case 1: When both A = B = 0.
  
  In this case the number of times the loop iterates = 0 as B = 0.
• Case 2: When A != 0 and B = 0.
  
  In this case also the number of times the loop iterates = 0 as B = 0.
• Case 3: When A = 0 and B != 0.
  
  In this case, the number of times the loop iterates = 1 because after the first iteration, the value of X = B as when you do the bitwise XOR of any binary number with 0 the result is the number itself. The value of Y = 0 because bitwise AND of any number with 0 is 0. So, you can see Y = 0 then B = 0 and Y << 1 = 0.
• Case 4: When A = B and A != 0 and B != 0.
  
  In this case, the number of times the loop iterates = 2 because in first iteration the value of A = 0, why because bitwise XOR of two same numbers is always 0 and value of Y = B because bitwise AND of two same numbers is the number itself and then B = Y << 1, after the first iteration, A = 0 and B != 0 so this case becomes Case-3. So, the number of iteration will always be 2.
• Case-5: When A != B and A != 0 and B != 0.
  
  In this case, the number of times the loop iterates = length of the longest carry-chain.

Algorithm to calculate the length of the longest carry-chain:

• First make both the binary strings A and B of equal length if they are not.

• As we know the length of the largest carry sequence will be the answer, I just need to find the maximum carry sequence length I have occurred till now. So, to compute that,

• I will iterate from left to right i.e. LSB to MSB and:

  • if carry + A[i] + B[i] == 2 means that bit marks the start of carry-sequence, so ++curr_carry_sequence and carry = 1.
  • if carry + A[i] + B[i] == 3 means the carry which was forwarded by previous bit addition is consumed here and this bit will generate a new carry so, length of carry-sequence will reset to 1 i.e. curr_carry_sequence = 1 and carry = 1.
  • if carry + A[i] + B[i] == 1 or 0 means carry generated by the previous bit resolves here and it will mark the end of the carry-sequence, so the length of the carry-sequence will reset to 0. i.e. curr_carry_sequence = 0 and carry = 0.

• Now if curr_carry_seq length is > than max_carry_sequence, then you update the max_carry_sequence.

• Answer would be max_carry_sequence + 1.

For Source-code refer to No Carry Adder Solution.

P.S. For average-case analysis of No-Carry Adder you can refer to the paper: Average Case Analysis of No Carry Adder: Addition in log(n) + O(1)Steps on Average: A Simple Analysis.

How many times the loop will execute in python?

for i in range(0,10):
    print(i)

Will output:

0
1
2
3
4
5
6
7
8
9

Why does the "for" loop execute one more time than the body of the loop?

That is because there is always one more evaluation of the condition of the loop than there are executions of the body of the loop.

Take this simple example:

x = 4
while x < 0:
    x += 1
    print('hello')

We can see that the body of the loop is never executed (0 times), while the exit condition of the loop is evaluated once(1 time).

So, in any situation, we have the following:

The body of the loop is executed once for every time the condition is evaluated to True

AND

The condition is one more time evaluated to False, for the program to exit the loop.

How many time is the inner loop running?

Let's look at the the two loops individually.

The outer loop starts with i=1, and increments it by k in each iteration, until it's greater than n. In other words it can run n/k times, or, to be accurate, floor(n/k) times, since a loop can't run a non-whole number of times.

The inner loop is relatively simpler - it starts with j=1 and increments it by one in each iteration until it's greater than k, for a total of k times.

Put these two together and you'll get floor(n/k)*k.

EDIT:

As pointed out in the comment, this analysis is true if n>=k. If n<k the outer loop will run exactly once. I.e., the total times run would be: max(1, floor(n/k))*k.

---

Related Topics