I had this question on a test and i'm trying to understand it:

What is the time complexity of this function (in the worst case) assuming that Bubblesort() is the most optimized version of the Bubble Sort algorithm?

def MultSort(a,n):
    for i in range(n):
        BubbleSort(a)

The options were:

• Linear
• Quadratic
• Cubic

I was thinking that the first sort (because it's the worst case) would be O(len(a)^2) and then n*O(len(a)) once it's ordered.But i can't really get to a result by myself

CodePudding user response：

The annoying thing in this exercise is that the answers to choose from do not indicate what the dimension of variation is by which the complexity would be linear, quadratic or cubic. There are two obvious candidates: len(a) and n. Since no distinction is made in the exercise, and no information is given as to whether one of the two is to be assumed constant, your best guess would be to assume they are equal (n = len(a)).

We could guess that n is given as a separate argument because the same function signature would be used in languages where there is no equivalent for the len() function, like for C arrays.

Anyway, with the assumption that n = len(a), here is what we can say:

the first sort (because it's the worst case) would be O(len(a)^2)

Yes, or in other words: O(