CODEWITHSUNDEEP
algorithmsortingdata-structurestime
Math4me
Math4me

Reputation: 155

Mergesort Variation - Time Complexity

Let's say we have a different variation of Mergesort:

MergesortVar(A,p,r)
  if p < r then
    q ← (p+r)/2
  Bubblesort(A, p, q)
  MergesortVar(A, q+1, r)
  Merge(A, p, q, r)

I want to analyze its time complexity for the best and worst cases.

So in general, we get here:

MergesortVar(A,p,r)         T(n)
  if p < r then             O(1)
    q ← (p+r)/2             O(1)
  Bubblesort(A, p, q)       T(n)
  MergesortVar(A, q+1, r)   T(n)
  Merge(A, p, q, r)         O(n)

So T(n)=2T(n)+c•n is that correct?

How can I then analyze its worst and best cases?

Thanks a lot!!

Upvotes: 0

Views: 41

Answers (1)

trincot
trincot

Reputation: 350310

The base case is missing in the pseudo code which is a major flaw, and unless you made errors in reproducing it faithfully, this should make you reconsider the quality of the course.

But possibly you got the indentation wrong, because the recursive call should never be made unconditionally. Here is a correction:

MergesortVar(A,p,r)
    if p < r then
        q ← (p+r)/2
        Bubblesort(A, p, q)
        MergesortVar(A, q+1, r)
        Merge(A, p, q, r)

Now to the complexities:

Bubblesort has a worst case complexity of O(𝑛²), and a best case complexity of O(𝑛), provided it does not continue its iterations when there is an iteration that makes no swaps.

Merge has a worst case complexity of O(𝑛). Depending on its implementation it could have a best case complexity of O(1), because when A[q] < A[q+1], there is nothing to do.

𝑛 is in this case the size of the given array, which is different for a recursive call.

BubbleSort is called on a subarray of size 𝑛/2, then 𝑛/4, then 𝑛/8, ... then 2. So the total time complexity of all BubbleSort calls together is:

Worst Case Best Case
O(𝑛²(1/4 + 1/4² + 1/4³ + ...)) O(𝑛(1/2 + 1/2² + 1/2³ + ...))
= O(𝑛²/3)
= O(𝑛²) = O(𝑛)

A similar reasoning goes for the total time complexity of all Merge calls together: it is called on a combined array size of 𝑛, then 𝑛/2, 𝑛/4, ...etc, log₂𝑛 times.

So that time complexity is:

Worst Case Best Case
O(𝑛(1 + 1/2 + 1/2²...) O(log₂𝑛)
= O(2𝑛)
= O(𝑛) =O(log𝑛)

Each recursive call of MergesortVar takes constant time if we exclude the time spent on BubbleSort and Merge, so we get a total time complexity for this overhead of O(log𝑛).

So we see that the time complexity of the Bubble Sort component is determining the overall time complexity:

Worst Case Best Case
O(𝑛²) + O(𝑛) + O(log𝑛) O(𝑛) + O(log𝑛) + O(log𝑛)
= O(𝑛²) = O(𝑛)

Upvotes: 1

Related Questions