View Single Post
NascentOxygen
NascentOxygen is offline
#2
Mar2-12, 09:25 PM
HW Helper
P: 4,716
Quote Quote by zeion View Post
Then, if I were to merge them sequentially, ie merge first two, then the third with the first two, the running time would be O(kn), since, the first two will take n comparisons, making a merged list of 2n elements,
okay
then compare to the next list of n elements takes n comparisons, and latch on the rest of the 2n list.
What if there is no "rest"? Maybe the n list has elements to be slotted throughout the 2n list?