# 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
{"ft_lang_label":"__label__en","ft_lang_prob":0.9411964,"math_prob":0.99610513,"size":730,"snap":"2021-04-2021-17","text_gpt3_token_len":204,"char_repetition_ratio":0.12534435,"word_repetition_ratio":0.0,"special_character_ratio":0.28630137,"punctuation_ratio":0.08176101,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99991393,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-01-19T22:12:58Z\",\"WARC-Record-ID\":\"<urn:uuid:7d8810c4-5764-4656-b456-8a9e9eb6c367>\",\"Content-Length\":\"122692\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:0cb8fd55-2c5e-4bdc-8533-6090ea3a4663>\",\"WARC-Concurrent-To\":\"<urn:uuid:2d657487-75a4-43a1-8394-07f72f8b0805>\",\"WARC-IP-Address\":\"151.101.129.69\",\"WARC-Target-URI\":\"https://cs.stackexchange.com/questions/110525/time-complexity-of-k-bubble-sort?noredirect=1\",\"WARC-Payload-Digest\":\"sha1:A2G4HKLUTGFHVS55B7CUQYVV2I43VWWC\",\"WARC-Block-Digest\":\"sha1:B3TXWOIT6GA3MYPEWYZUH36WZR2CUEZ4\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-04/CC-MAIN-2021-04_segments_1610703519784.35_warc_CC-MAIN-20210119201033-20210119231033-00244.warc.gz\"}"}