1
$\begingroup$

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.

Improve this question
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Optidad Jun 11 '19 at 14:58
  • $\begingroup$ @Vince Brilliant! I got it. thanks. $\endgroup$ – Peyman Jun 11 '19 at 15:21