Complexity of bucket sort with a known upper bound?

Question

Say we have an array that we know all the elements are 0...2n and are not ordered.

If we use a bucket sort algorithm with the complexity of O(n+k) where k is the range of the elements, which in this case is 2n, would the complexity to sort this array be Θ(n)?

My rationale is that the runtime is O(n + 2n), which si the same as O(3n), and since 3 is just a coefficient the complexity would be Θ(n).

Is this analysis accurate?

Answer 1

Yes, your analysis is correct. Counting sort's runtime is Θ(n + k), where n is the number of elements and k is the number of buckets. If the maximum value is cn for any fixed constant c, then the runtime of counting sort will be Θ(n), as you've mentioned.

Hope this helps!