The following codes must be done in C 1 Consider the followi

The following codes must be done in C++

1. Consider the following two loops:
// Loop A
for (i = 1; i <= n; i++)
for (j = 1; j <= 10000; j++)
sum = sum + j;
// Loop B
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
sum = sum + j;
What is the Big O of each loop? Design and implement an experiment to fi nd a value of n for which Loop B is
faster than Loop A.

2. Repeat the previous project, but use the following for Loop B:
// Loop B
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
for (k = 1; k <= j; k++)
sum = sum + k;

Solution

1)

Firstly i would like to explain you how BigO of a nested loop is calculated.

if a loop is like this nested loop

for(i=0:i<=n;i++)

{

for(j=0;j<n;j++)

{

//Some Operation

}

}

In this nested loops the total complexity Big O is calculated by product of total number of iterations done by the each and every loop. for example for the above example the complexity is O(n*n)=O(n^₂).

in your given problem

in LOOP A:

in LOOP B:

Comparing LoopA with LoopB:

The value of n for which LoopB executes faster than LoopA is 0>n<10000

2)

In this problem

LoopA:

LoopB:

The value of n for which LoopB executes faster than LoopA is for all n>=j, 0>n<10000.