3,717 views
3 votes
3 votes

Consider the following statement:
S1: Merge sort on linked list take O(n log n) time to sort input of length n.
S2: Merge sort on linked list give better space complexity then on array.
S3: Inplace merge sort on array will take O(n2) time.
Which of the following is correct?

a)S1

b)S1 and S2

c)S1,S2,S3

d) None

3 Answers

3 votes
3 votes

Option C is correct. All S1, S2 and S3 are correct.

S1:Merge sort on linked list take O(n log n) time to sort input of length n:- first for given n length string we have to divide in 2 halves then merge sorted subarray similarly out place array(create a dummy node and compare first element of 2 sorted linked list and map smallest one in dummy node and then so on....). for division- log n time and merging n time. So time complexity= O(nlogn)

S2:The mergesort algorithm is recursive, so it requires O(log n) stack space, for both the array and linked list cases. But the array case also allocates an additional O(n) space, which dominates the O(log n) space required for the stack. So the array version is O(n), and the linked list version is O(log n).

https://stackoverflow.com/questions/24171242/why-is-mergesort-space-complexity-ologn-with-linked-lists#:~:text=The%20mergesort%20algorithm%20is%20recursive,is%20O(log%20n).

 

S3: Inplace merge sort on array will take O(n^2) time. This is true statement, just try it.

2 votes
2 votes
S3 is correct

In above question, there is no option given related to only s3 .

That's why option d is correct .

.
0 votes
0 votes
S1 : merge sort on linked list take O(nlogn)

S2: If we talk about Extra space then, in array it is O(n) and in case of linked list it is O(logn) . So,  linked list have less space complexity.

S3: Inplace algo recurrence relation :

     2T(n/2) +n²= O(n²)

So,  S1, S2, S3 all are correct

Related questions

4 votes
4 votes
1 answer
1
Shivi rao asked Oct 10, 2017
1,513 views
True or FalseMerge sort on Linked list takes O(nlogn)
0 votes
0 votes
1 answer
2
suneetha asked Nov 3, 2018
430 views
given n elements merge them into one sorted list using merge procedure then what is the time complexity for this ?explain with example
0 votes
0 votes
3 answers
3
aditi19 asked Oct 6, 2018
1,128 views
what is the recurrence relation for merge sort?
0 votes
0 votes
1 answer
4
shipra tressa asked Sep 15, 2018
545 views
n sorted subarrays each of size log n. find single sorted array with all elements.find time complexity