# time complexity of k-bubble sort [duplicate]

I'm a student. today I answered a question wrong, the question is this:

Spouse we have a k-bubble sort, which means except sorting 2 elements each time, it has a magical function that can sort $$k$$ elements each time with $$O(1)$$.

What is the best time complexity we can give from this sort? (you can use just the magical function)

I answered it $$O(\frac{n^2}{k})$$ because I thought that with $$O(\frac{n}{k})$$ times using the magical function we can sort the maximum number, so we repeat it $$O(n)$$ times to sort it completely. that's $$O(n)\times O(\frac{n}{k}) = O(\frac{n^2}{k})$$.

But seems that I was wrong and the right answer is $$O(\frac{n^2}{k^2})$$.

So I'm here for some help because I can't solve it myself. thanks in advance.

• instead of sorting the maximum number, sort the $k/2$ largest numbers, doing $k/2$ overlaps. Exactly this question has been asked some times ago, but I cannot find it. – Optidad Jun 11 '19 at 14:58
• @Vince Brilliant! I got it. thanks. – Peyman Jun 11 '19 at 15:21