GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
166 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 (56.4k points)   | 166 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


Top Users Aug 2017
  1. ABKUNDAN

    4658 Points

  2. Bikram

    4032 Points

  3. akash.dinkar12

    3136 Points

  4. rahul sharma 5

    2856 Points

  5. manu00x

    2664 Points

  6. makhdoom ghaya

    2380 Points

  7. just_bhavana

    2040 Points

  8. Tesla!

    1756 Points

  9. pawan kumarln

    1574 Points

  10. learner_geek

    1558 Points


24,878 questions
31,952 answers
74,105 comments
30,065 users