Find the worst-case run-time of each of the situations below. Justify your answe

Question

Find the worst-case run-time of each of the situations below. Justify your answer.

(1) Merge sort, but splitting into three arrays instead of two (i.e. each array is N/3 instead of N/2 size). You may assume the original size of the array is a power of 3.

(2) Merge sort, except using insertion sort immediately instead of recursively calling merge sort. (Thus no recursion ever happens.)

(3) The algorithm in “Problem4Sort.java”.

(4) Some algorithm with a recursive property: T(n) = 10 T(n/3) + O(n lg n)

Problem4Sort.java:

Explanation / Answer

Hi,

There are multiple questions in this, as per chegg policy, we are supposed to answer only one per answer, please post others as a separate question, we will be happy to assist you :)

1. Now given, array is divided into 3 parts instead of two, first lets recap the original merge sort, where in, we divide the array repeatedly into 2 halves i.e array becomes n->n/2->n/4... which evaluates to log n steps,

now, if we do the same but with 3 parts, it will become n,n/3,n/9... that is essentially this also evaluates t log n but with base 3, and then merging them takes 2 comparisons rathere than 1(which makes this a little costlier, but not more than N anyway), hence the worst case complexity will remains

O(n log3 n) - notice the change in base



Thumbs up if this was helpful, otherwise let me know in comments

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

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