Textbook: Introduction to Algorithms (3rd edition) by T. Cormen, C. Leiserson, R

Question

Textbook: Introduction to Algorithms (3rd edition) by T. Cormen, C. Leiserson, R. Rivest and C. Stein, MIT Press, 2009

Show all work (if necessary).

So far, we only covered insertion-sort and merge-sort in class. Do not use other sorting algorithms.

3. Give the running time at each step of the following high-level description of an algorithm, along with the total running time, briefly justifying each step. The input is an array with n items. The array is scanned left-to-right (that is, we have a for loop fron i = 0 to n-1), and at each iteration we do the following a) Set AU] Aj] mod Ali] for all 0 SjSn-1. b) Sort the resulting array A. Solution. Your solution here

Explanation / Answer

Step (a) takes O(n) time as it runs for every j lying in [0, n-1]

Step (b) will take O(n*logn) if we use merge sort. If we use insertion sort its complexity will be O(n^2).

Now total running time is evaluated as below:

a) and b) are inside a for loop which is indexed over i lying in [0,n-1]. Thus a) and b) runs for n times. So if we use merge sort in Step b), then total run time = n*[Run time of Step (a) + Run Time of Step(b)]

= n[O(n) + O(n*log(n))] = O(n^2log(n)) (O(n) is subset of O(n*logn))

If we use Insertion sort, above becomes)

n[O(n) + O(n^2)] = O(n^3)

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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