What is the complexity of this specialized sort

Question

I would like to know the complexity (as in O(...) ) of the following sorting algorithm:

• There are B barrels
• that contain a total of N elements, spread unevenly across the barrels.
• The elements in each barrel are already sorted.

The sort combines all the elements from each barrel in a single sorted list:

• using an array of size B to store the last sorted element of each barrel (starting at 0)
• check each barrel (at the last stored index) and find the smallest element
• copy the element in the final sorted array, increment the array counter
• increment the last sorted element for the barrel we picked from
• perform those steps N times

or in pseudo code:

for i from 0 to N
    smallest = MAX_ELEMENT
    foreach b in B
        if bIndex[b] < b.length && b[bIndex[b]] < smallest
            smallest_barrel = b
            smallest = b[bIndex[b]]
    result[i] = smallest
    bIndex[smallest_barrel] += 1

I thought that the complexity would be O(n), but the problem I have with finding the complexity is that if B grows, it has a larger impact than if N grows because it adds another round in the B loop. But maybe that has no effect on the complexity?

Answer 1

Since you already have pseudo-code, finding the complexity is easy. You have 2 nested loops. The outer one always runs N-1 times, the inner always |B|, where |B| is the size of the set B (number of barrels). Therefore the complexity is (N-1)*|B| which is O(NB).

Answer 2

You are correct that the number of barrels changes the complexity. Just look at Your pseudocode. For every element You are about to pick, You have to search the array of candidates, the length of which is B. So You are performing an operation of complexity O(B) N times