CODEWITHSUNDEEP
java
user5556360
user5556360

Reputation:

Merge of sorted and unsorted linked lists in java implementation

I was reading about sorted linked lists and unsorted sorted lists ... I found this table http://bigocheatsheet.com/

I do not understand what they mean by saying in the third table that a sorted linked list has Merge of O(m+n) while an unsorted sorted list has Merge of O(1)!

What does that mean?

thanks

Upvotes: 1

Views: 294

Answers (1)

ControlAltDel
ControlAltDel

Reputation: 35011

It's saying that the optimal time to merge a sorted list is O(m + n), because you have to traverse both lists, compare the top/bottom and decide which is higher / lower. Unsorted list could in theory be merged in O(1) if this is a linked list... you just point the tail of the first linked list to the second linked list

Upvotes: 1

Related Questions