How can the complexity of sorting the bucket O (n + k)?

Question

Before saying “this was asked earlier” or “finding a book of algorithms”, please read and tell me what part of my reasoning went wrong?

Say that you have n intermediaries and you divided them into k bins, it will take O (n) time. However, you need to sort each of the k bins, if you use quick sort for each bunker, this is O ((n / k) log (n / k)), so this step will take O (nlog (n / k) + to). Finally, you need to collect this array, it will take O (n + k), (see this post ), so the general operation will be equal to O (n + nlog (n / k) + k). Now, as this nlog (n / k) disappeared, I could not understand at all. I guess there is some kind of math that eliminates this n * log (n / k). Can anybody help?

Answer 1

Your guess:

• k - number of buckets - random

wrong.

There are two options for sorting the bucket, so it's pretty confusing.

---

A

The number of buckets is equal to the number of elements at the entrance

See analysis here

---

IN

The number of buckets is equal to R - the number of possible values ​​for integers

See analysis here and here.

Answer 2

Your error suggests that quicksort is used to sort buckets. This is usually not the case, and how do you avoid the terms (n / k) log(n / k) .

Answer 3

Your analysis looks good. The term Bucketsort is used for many different algorithms, so depending on which one you looked at its average execution time, it may be O (n + k) or not.

If I were to guess, you could look at a typical option, where we choose k very large so that n / k will be a constant. In another popular variant, even k → n, therefore, buckets are divided into k / n instead.

If you give in detail an algorithm and a source that claims to be on average O (n + k), I can return to my answer.