For this program fragment you will (a) write down the total work done by each pr

Question

For this program fragment you will (a) write down the total work done by each program statement (beside each statement), (b) compute an expression for the total time complexity, T(n) and derive thhe big Oh complexity, showing all steps to the final answer.

int sortedArray [];

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

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

readArray(a) // reads in an array of n values

sortedArray = sort(a) // sort() takes n log n operations

}

}

by the way the readArray and sortedArray methods are in the loops, somehow when I posted it, the spaces didnt work.

Explanation / Answer

1////for ( i = 0; i < n; i++) { [This line will execute n times ]

2//// for ( j = 0; j < i; j++) { [This will in total execute n(n+1)/2 times ]

3////       readArray(a) // reads in an array of n values

4////        sortedArray = sort(a) // sort() takes n log n operations

}

}

So if we look closer 1st line will execute n times and second line will execute n(n+1)/2 times.

like this

when i = 0 execution statements = 0 because j < i
when i = 1 execution statements = 1 because j < i
when i = 2 execution statements = 2 because j < i
-------------------------------------------------
when i = n execution statements = 0 because j < n

so total 1+2+3+....+n = n(n+1)/2

So complexity of outer plus inner = O(n^2) + O(n) [Outer loop will execute n times] = O(n^2)

so both for loops will give O(n^2) complexity but we have 2 more statements related to array also.

n^2 * nlogn = n^3logn

so complexity will be O(n^3logn)

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.