stuck with homework problem Sort assumes that each of n input elements in array

Question

stuck with homework problem

Sort assumes that each of n input elements in array A is an integer in the range 0 to k, where k = 0(r). The array B holds the sorted output, and array C provides temporary working storage. Sort(A, B, k) let CIO.. k be a new array for i = 0 to k C[i] = 0 4for j- 1 to A.length for i= 1 to k 8 forj Alength downto 1 for j- A.length downto 1 C[i] = C[i] + Cli-1 1 10 Assuming Integer-Sort is correct, which of the three asymptotic statements, A, B, C or D describes its worst-case run time? A (n') nlgn C O(n) none of the above

Explanation / Answer

Given k = O(n2) implies k <= c n2 , where c is a constant

also given we need to find the worst case run time,

this implies that k will be very near to n2 (for the worst case).

Let us take k = c n2.

In the above algorithm we have 4 for loops, let us consider each loop running time

1st for loop :-

        for i = 0 to k

              C[i] = 0

This loop executes k times , here k is cn2 hence this loop complexity is O(n2).

2nd for loop :-

        for j = 1 to A.length

              C[A[j]] = C[A[j]] + 1

This loop executes A.length times ,given A is of n lenght hence this loop complexity is O(n).

3rd for loop :-

        for i = 1 to k

              C[i] = C[i] + C[i-1]

This loop executes k times , here k is cn2 hence this loop complexity is O(n2).

4th for loop :-

        for j = A.length downto 1

            B[C[A[j]]] = A[j]

            C[A[j]] = C[A[j]] - 1

This loop executes A.length times ,given A is of n lenght hence this loop complexity is O(n).

Hence the overall complexity of the algorithm is = c1n2 + c2n + c3 n2 + c4n

                                                                     = O(n2).

Hence none of the above is the answer.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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