Time complexity of operations on a sorted array of sorted lists

An answer to this question on Stack Overflow.

Question

I have a sorted array of N elements equally distributed in K lists that is also sorted. What will be the time complexity (in tightest Big-O notation) for:

  1. Removing the smallest element.
  2. Resorting array after the removal of the smallest element.
  3. Removing all N elements

For the first part, I thought the answer is O(1) since the smallest element is the first element. But the list that it's a part of need not be the first list and so I am unsure.

For the second part, I am not sure (maybe O(NK)?)

For the third part, it has to be O(N) since we're going through the entire array but, again, I am unsure

Answer

It depends on what you mean when you say that the "K lists [are] also sorted".

If the numbers are distributed randomly throughout the K lists, but each of the K lists is itself sorted, then it will take O(K) time to look at the head of all the lists to identify the smallest element. However, if the numbers are divided between the K lists such that the K lists A,B,C,... can be ordered such that A0<=AN<=B0<=BN<=C0<=CN..., then it takes O(1) time to find the smallest element because you know it is at the head of the first list.

Removing either the smallest or largest element of the array preserves the existing sorted order, so this takes time O(1).

The time it takes to "remove" all the elements depends on your model of computation. It could take O(1) time if removal counts as simply disposing of the whole data structure. However, if each element requires individual clean-up, then it will take O(N+K) time: O(N) for the cost of accessing each element and O(K) for the cost of accessing each of the lists.