Time complexity for partitioning a set and sorting the partition's subsets-CodePudding

Suppose I have a function which partitions set S, |S|=n, into S/subsetSize subsets of size subsetSize and sorts each subset:

partitionAndSort(Set s, int subsetSize) {
   List partition = partitionList(s);
   for(Set subset: partition) {
      sort(subset);
   }
}

What's the running time of the function?

partition clearly takes O(n) because we go through the elements of the set one by one. subsetSize is considered to be a constant, hence an individual sort takes O(subsetSize*log(subsetSize))=O(1), and there are O(n/subsetSize)=O(n) sorting calls. Does the overall sorting take O(n)? Does that give a running time of O(n) for the function?

CodePudding user response：

Yes, your function only needs O(n). Bear in mind, though, that it's not sorting the given set. Only the subsets. Hence there's no conflict with the n log n lower bound for (comparison-based) sorting of a set of n values, as you're not doing that.