Question

NEED IN C++

For the following programming problems, you need to time a section of code in C++. For example, the following statements time the execution of the function doSomething:

#include

clock_t start = clock();

doSomething();

clock_t finish = clock();

double overallTime = static_cast(finish - start)/ CLOCKS_PER_SEC;

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 us the Big O of each loop? Design and implement an experiment to find 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;

3. Write a C++ program that implements the following three algorithms and times for various values of n. The program should display a table of the run times of each algorithm for various values of n.

//Algorithm A          //Algorithm B       //Algorithm C

sum = 0;               sum = 0;            sum = n * (n + 1) / 2

for(i = 1 to n)        for(i = 1 to n)    

   sum = sum + 1      {

                       for(j = 1 to i)

                         sum = sum + i

                       }

Expected Outputs:

Sum

	#1		#2
Input size n	Loop A	Loop B	Loop A	Loop B2
3
10
100
1000
100000
1000000

Running time (milliseconds)

	#1		#2
Input size n	Loop A	Loop B	Loop A	Loop B2
3
10
100
1000
100000
1000000

Sum

	#3
Input size n	Algorithm A	Algorithm B	Algorithm C
3
10
100
1000
100000
1000000

Running time (milliseconds)

	#3
Input size n	Algorithm A	Algorithm B	Algorithm C
3
10
100
1000
100000
1000000

Answer 1

Please give thumbs up if you like it

1)SUM

=> Loop A Sum will be = N * (10000 * 10001)/2 = N * 25002500

=> Loop B Sum will be = N * (N* (N+1))/2

=> Loop B2 Sum will be = N * (N * (N +1)*(N+2))/6

substitute value of N in those formula and get sum value

Input Size N	Loop A	Loop B	Loop B2
3	75007500	18	30
10	250025000	550	2200
100	2500250000	5500	22000
1000	25002500000	55000	220000
100000	2500250000000	5500000	22000000
1000000	25002500000000	55000000	220000000

2) Running Time

=>Loop A running time is =10000*N

=>Loop B running time is =N*N

=>Loop A running time is =N*N*(N+1) /2

substitute value of N in those formula and get running time value

Input Size N	Loop A	Loop B	Loop B2
3	30000	9	18
10	100000	100	550
100	1000000	10000	5500
1000	10000000	1000000	55000
100000	1000000000	10000000000	5500000
1000000	10000000000	1000000000000	55000000

3) Sum

=> Algorithm A Sum value is = N

=> Algorithm B Sum value is = N * (N+1) * (2N + 1)/6

=> Algorithm C Sum value is = N*(N+1)/2

substitute value of N in those formula and get sum value

Input Size N	Alogrithm A	Algorithm B	Algorithm C
3	3	14	6
10	10	385	55
100	100	338350	5050
1000	1000	333833500	500500
100000	100000	333338333350000	50000 * 100001
1000000	1000000	333333833333499970	500000 *1000001

4) Running Time

=> Algorithm A Running Time is = N

=> Algorithm B Running Time is = N * N

=> Algorithm C Running Time is = constant

substitute value of N in those formula and get running time value

Input Size N	Algorithm A	Algorithm B	Algorithm C
3	3	9	constant
10	10	100	constant
100	100	10000	constant
1000	1000	1000000	constant
100000	100000	10000000000	constant
1000000	1000000	1000000000000	constant