CODEWITHSUNDEEP
algorithmsortingtime-complexitymergesort
user4058730
user4058730

Reputation:

Merge Sort Algorithm Dilemma

Consider a recursive implementation of Merge Sort which is used to sort an array of size n. The number of recursive calls made to Merge Sort is

either O(n) but not Theta(n)

or Theta(n)

or O(n log n) but not Theta(n log n)

or Theta(n log n)

PS : I am preparing for an exam and found this question, What I am thinking is that merge sort has a time complexity of Theta(n log n) but in that we have not considered the constants. So, it should be O(n log n) but not Theta(n log n). But that is a wrong answer. What should be the correct answer and why?

Upvotes: 2

Views: 586

Answers (4)

luk32
luk32

Reputation: 16090

It's Theta(n).

Detailed explanation.

The number of operations will be Theta(n log n), because at each level of recursion you will perform Merges on the elements number summing up to n, and Merge has a complexity of Theta(n). That gives Theta(n) per level of recursion and you have log(n) levels which in total gives Theta(n log n).

However, you are not supposed to give complexity for number of operations (which depends on Theta(Merge)), but number of MergeSort calls. This is different.

user1990169 gives a very nice explanation how calculate the number of MergeSort calls. People seem to confuse it with number of operations, which is different.

Refer to the algorithm layout, where are Merge calls and where are MergeSort calls.

Why different answers are right or wrong?

A) O(n) but not Theta(n)

B) Theta(n)

C) O(n log n) but not Theta(n log n)

D) Theta(n log n)

Strictly speaking, in plain english. If Theta(f(x)) = Theta(g(x)) it means that f(x) is asymptotically not lower, and not greater that g(x). If f(x) belongs to O(g(x)) it "just" means f(x) will is asymptotically not greater than g(x).

The difference is: You can say that f(n) is O(n) as well as O(n^2) (it is not greater in both cases). But you cannot say f(n) is Theta(n^2). That being said, I don't know anyone with algorithmic background who would use BigO in such way, everyone uses it as a tight bound (like Theta).

So anything saying it is not Theta(n), or saying it is Theta( something asymptotically else ) is wrong (A and D). B is right.

C is "debatable". Technically I would say it's right too. Because n is asymptotically smaller or equal to n log n (Big O formal definition), also it is not equal to n log n (Theta formal definition). You can refer to wikipedia they use similar example.

Upvotes: 1

Abhishek Bansal
Abhishek Bansal

Reputation: 12705

At each level of recursion, you call two instances of Mergesort. Also, the recursion depth is log(n)

Hence the number of calls to MergeSort = 2 + 4 + 8 + ... + 2^(logn)
                                       = 2 * ( 2^logn - 1 ) / (2 - 1)
                                       = 2 * (n - 1 )
                                       = Theta(N)

So the number of calls is Theta(N). However, the overall time complexity of the algorithm is Theta(NlogN) because at each depth in the recursion, you perform Theta(N) steps for merging the sorted arrays and the total depth of the recursion tree is Theta(logN).

Upvotes: 4

Murtaza Zaidi
Murtaza Zaidi

Reputation: 597

In Merge Sort we need to sort two entries at each step and merge them. It doesn't care if array is sorted or completely shuffled. Its worst case and best case both are n log(n). Therefore its Theta(nlog(n))

Upvotes: -1

Haris
Haris

Reputation: 12272

Not considering the constants does not change the time complexity, it just means that whatever size of input n that you give, the constants will not have significant impact on the time complexity. Or in other words, time complexity depends on the size of the input, and constants is independent of the size of the input, therefore it does'nt effect the time complexity..

Upvotes: 0

Related Questions