Question

For each of the following program fragments, give an analysis of the running time (Big-Oh will do).

Give the exact value leading to the Big-Oh conclusion, and show your work.

sum = 0; //1

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

++sum;

sum = 0; //2

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

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

++sum;

sum = 0; //3

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

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

++sum;

sum = 0; //4

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

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

++sum;

sum = 0; //5

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

for( j = 0; j < i * i; ++j )

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

++sum;

Answer 1

/*1. O(n) is time complexity for the given program.
because the value of 'i' ranges from o to (n-1) and sum will be n for i=(n-1).
*/
sum = 0;
for( i = 0; i < n; ++i )
++sum;
/*2. O(n^2) is time complexity for the given program.
for every value of i(ranges 0 to n-1), j ranges from(0 to (n-1)).
*/
sum = 0; //2
for( i = 0; i < n; ++i )
for( j = 0; j < n; ++j )
++sum;
/*3. O(n^3) is the time complexity for the given program.
for every value of i(ranges from 0 to n-1), j will range from 0 to n^2.
*/
sum = 0;
for( i = 0; i < n; ++i )
for( j = 0; j < n * n; ++j )
++sum;
/*4. O(n^2) is the time complexity of given program.
for each vaue of i(ranges from o to (n-1)), j will range from o to (i-1).
No. of times inner loop gets evaluated is 1+2+...+(n-1)=(n-1)*n/2.
*/
sum = 0;
for( i = 0; i < n; ++i )
for(j = 0; j < i; ++j )
++sum;
/*5. O(n^4) is the time complexity of the given program.
For each value of i(ranges from 0 to (n-1)), j ranges 0 to i^2 and k ranges from 0 to j;
for i=n, second loop(j ranges from 0 to n^2) and the third loop(k ranges also from 0 to n^2).
(n-1)^2*(n-1)^2
*/
sum = 0;
for( i = 0; i < n; ++i )
for( j = 0; j < i * i; ++j )
for( k = 0; k < j; ++k )
++sum;