0

We know that merge sort has time complexity O(nlogn) for the below algorithm:

void mergesort(n elements) {
mergesort(left half);  ------------ (1)
mergesort(right half); ------------(2)
merge(left half, right half);

What will be the Time complexities for the following implementations?

(1)
void mergesort(n elements) {
    mergesort(first quarter);  ------------ (1)
    mergesort(remaining three quarters); ------------(2)
    merge(first quarter, remaining three quarters);

(2)
void mergesort(n elements) {
    mergesort(first quarter);  ------------ (1)
    mergesort(second quarter); ------------(2)
    mergesort(third quarter);  ------------ (3)
    mergesort(fourth quarter); ------------(4)
    merge(first quarter, second quarter,third quarter, fourth quarter);

Please elaborate how you find the complexities.

Improve this question
2
  • 3
    This seems to be a homework question. No problem with that but at least explain what you think about. We are not here to give you a ready-to-copy-paste answer. Commented Oct 14, 2013 at 9:58
  • I have a smilar , not the same problem as homework. I calculated the recurrance relation and got the answer to be nlogn each time. Found that strange. Commented Oct 14, 2013 at 10:09

3 Answers 3

Reset to default
4

Still O (n log n) because log base 4 of n = log n / log 4, which ends up being a constant.

[EDIT]

The recurence relation of the merge sort algorithm with k split is as follows. I assume that merging k sorted arrays with a total of n elements cost n log2(k), log2 representing log base 2.

T(1) = 0
T(n) = n log2(k) + k T(n/k)

I could resolve the recurence relation to:

T(n) = n log2(n)

regardless of the value of k.

Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

So how does the relation look like, once we increase the no. of intervals? What I saw is that the denominator increases, decreasing the time complexity ?
For 2 intervals we have T(n) = T(n/2) + T(n/2) + n. How will the relation look for 4 intervals? T(n) = 4T(n/4) + what ? WHat will be the merging step's complexity in terms of n ?
It will be faster by a constant factor of log 4 / log 2, but still O(n log n)
I dont think it will be faster. The merging step will infact be slower thus increasing the overall complexity.
I did not quiet get what is the difference between complexity and performance. Can you please explain the same with this case ?
|
3

Note that this is not exact answer to your question but a hint.

First we need to understand how time complexity for default merge sort comes out to be n(log n).

If we have 8 elements and by default mergesort approach, if we go on dividing them half each time till we reach group containing only one element, it will takes us 3 steps.

So it means mergersort is called 3 times on N elements. thats why time complexity is 3*8 i.e. (log N)*N

enter image description here

If you are changing default partition from half to other proportion, you will have to count, how many steps it take for you to reach group of 1 elements.

Also note that this answer only aims to explain how complexity is calculated. Big O complexity of all the partition approach is same and even other 2 partition if implemented in efficient way will have exact complexity of N(logN)

Improve this answer

1 Comment

However wont the merging step's complexity increase? Thus increasing the overall complexity as we increase the number of intervals.
2

All three of the algorithms you posted are O(n log n), just with slightly different constants.

The basic idea is that it takes log(n) passes, and in each pass you examine n items. It doesn't matter how large your partitions are, and in fact you can have varying sized partitions. It always works out to O(n log n).

The runtime difference will be in the merge method. Merging sorted lists is an O(n log k) operation, where n is the total number of items to be merged, and k is the number of lists. So merging two lists is n * log(2), which works out to n (because log2(2) == 1).

See my answer to How to sort K sorted arrays, with MERGE SORT for more information.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.