educative.io

Time complexity of merging k sorted lists

Courses
,
#1

Problem statement: Given an array of k sorted linked lists, your task is to merge them into a single sorted linked list and return the head of this linked list.

Recommended solution: Iteratively merge pairs of lists.

Time complexity: “The time complexity is O(nlogk), where k is the number of the lists and n is the maximum length of a single list.”

Should this be O(nklogk)? Take for example k = 8, n = 100. We’ll process all 800 elements a total of three times, meaning 100 * 8 * log8 = nklogk.

Course: Grokking Coding Interview Patterns in Python - Learn Interactively
Lesson: Solution: Merge K Sorted Lists

1 Like
#2

Hello @Isaac_Haseley,

Thank you for your question regarding the time complexity of the merge k sorted linked lists algorithm. Your thought process is insightful, but there’s a subtle aspect to consider that leads to a different complexity.

The time complexity of this algorithm is O(n log k), not O(nk log k).

  1. Total Nodes: The total number of nodes across all lists is n.
  2. Number of Lists: Initially, there are k lists.
  3. Merging Process: Each node is involved in one merge operation per round, not processed k times per round.
  4. Halving the Number of Lists: The number of lists is halved in each round, so there are log k rounds of merging.
  5. Complexity per Round: Each round of merging has a complexity of O(n), as each node is part of one merge operation.
  6. Total Complexity: With O(log k) rounds, each having a complexity of O(n), the

I hope this clarifies the complexity analysis of the algorithm. If you have any further questions or need more explanation, feel free to ask. We’d be happy to help. Thanks!

Happy learning!

#3

Thanks @Dian_Us_Suqlain!

  1. Total Nodes: The total number of nodes across all lists is n.

From the lesson:

n is the maximum length of a single list

1 Like
#4

You’re welcome @Isaac_Haseley! And thank you for pointing this out, we’ll fix this statement in the lesson.