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 with in depth analysis

- 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.

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

- The algorithm in “Code3” below.

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

code:

Explanation / Answer

The complexity of merge sort will be same in each case whether it's best worst or average.

But the base for the term of complexity will be changed .

Let's see how to do that when the partition is done in 3 parts.

So

if some algorithm is  T(n) = 10 T(n/3) + O(n lg n)

so the complexity is nlog3n .

we know that -

then

. If f(n) = ?(nc) where c < Logba then T(n) = ?(nLogba)

2. If f(n) = ?(nc) where c = Logba then T(n) = ?(ncLog n)

3.If f(n) = ?(nc) where c > Logba then T(n) = ?(f(n))

using master theoremm

so in

T(n) = 10 T(n/3) + O(n lg n)

a=10 , b= 3 , k=1 , c=1 and logba=log310>2 that means c < Logba , so complexity O(n*log3n).

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

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