0

Let's say there is a singly linked list with X elements (X is super-large number).

First, we need to traverse the list from start to the end, which takes O(n) time.

Then, it takes ~~ time. (I don't get this part. I was thinking about merge sort because I remember that it takes O(n logn) time to sort, but I wasn't sure either I can do this on singly linked list or not)

After we finish sort it in descending order, it will take O(1)

Can this be faster than O(n^2) by any chances?

huza
  • 107
  • 6

1 Answers1

0

Perhaps, it's the best to keep list sorted when inserting elements. I'm not sure that mergesort would be O(N*log(N)) with linked list and there is a lot of work with pointers, so it's not very simple.

Stefan Golubović
  • 1,225
  • 1
  • 16
  • 21