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
Advertisement
Answer
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(𝑛²)
and then n*O(len(a)) once it’s ordered.
Yes, or in other words: 𝑛O(𝑛) = O(𝑛²)
But i can’t really get to a result…
The final step is to add these two phases that you have analysed, so here is a spoiler in case you don’t see how those can be added:
O(𝑛²) + O(𝑛²) = O(𝑛²)
…which means the anser is:
Quadratic