[INTERESTING] What's the time complexity for this problem?

help
1

This is the problem to flatten the linked lists.

I thinks the time complexity is O(n^2) , where n is no. of nodes.

If we consider average length of linked list to be k, then for merging 1st 2 list the time complexity is 2k, and for merging resultant with the next its 3k and so on
so 2k + 3k+ … + (no. of lists )

and no. of lists = n/k = m

so it would be O((m(m+1)/2)k) which would be O(m^2k) => O(n^2/k) => O(n^2).

What do you say ?

2

You analysis is right time is = 2k+3k+4k…mK= mmk and as n=mk so mmk can be nn/k or O(n*m) which is also given as expected one [here] (Flattening a Linked List | Practice | GeeksforGeeks) and space complexity is O(1)

But I think it can be done using heaps in O(n log m) time and O(m) space.