GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
129 views

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

asked in DS by Veteran (53.7k points)   | 129 views
@Srestha and @santhos i think option d) is correct .??
Could you explain

How S1 will be correct?
see the link @Deepak

How S1 and S2 are not correct ?

 

1 Answer

+1 vote
S3 is correct

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

That's why option d is correct .

.
answered by Active (1.3k points)  
@ 2-way mege sort is inplace sorting algorithm

and its worst case time complexity is O(nlogn).

we can implement Merge sort using linked lists in O(nlogn) time

Related questions

0 votes
0 answers
1
asked in Algorithms by pC Veteran (20.3k points)   | 49 views
0 votes
2 answers
2
asked in Algorithms by Arnabi Boss (5.9k points)   | 60 views
0 votes
2 answers
3
asked in Programming by harshit agarwal (379 points)   | 75 views


Top Users May 2017
  1. akash.dinkar12

    3154 Points

  2. pawan kumarln

    1630 Points

  3. sh!va

    1590 Points

  4. Arjun

    1350 Points

  5. Devshree Dubey

    1246 Points

  6. Angkit

    1044 Points

  7. Debashish Deka

    1022 Points

  8. Bikram

    972 Points

  9. LeenSharma

    836 Points

  10. Prashant.

    692 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 May 22 - 28
  1. pawan kumarln

    256 Points

  2. Ahwan

    236 Points

  3. jjayantamahata

    114 Points

  4. joshi_nitish

    114 Points

  5. Arnab Bhadra

    94 Points


22,731 questions
29,061 answers
65,101 comments
27,627 users