An array A is c-nice, where c is a constant (e.g., c = 100), if for all 1 = i, j

Question

An array A is c-nice, where c is a constant (e.g., c = 100), if for all 1 = i, j = n, such that j -i = c, we have that A[i] = A[j]. For example, 1-nice array is already sorted. In this problem we will sort such c-nice array A using InsertionSort and QuickSort, and compare the results.
(a) In asymptotic notation (remember, c is a constant) what is the worst-case running time of
InsertionSort on a c-nice array? Be sure to justify your answer.
(b) Suppose that you know that the input array is c-nice. How would you choose the pivot for Quicksort? With this choice, what is the worst-case running time? You need not give a rigorous proof of your answer, but give a plausible argument.
(c) Which algorithm would you prefer?

Explanation / Answer

I don't know the answer but did find this piece of helpful info for ya: For the running times in parts (a) and (b) all you have to specify is the dependence of the running time on n for a fixed value of c; you do not have to say how the running time depends on c

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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