Q6 /20 We have an array that contains n integers between 0 and k (inclusive).

Radix sort processes each digit position independently. For n integers with values up to k, we need d = log₁₀(k) digit passes. Each pass performs a counting sort on n elements in O(n + base) time, where base is the radix. Across all d passes, the total complexity is O(d × (n + base)). Since d = O(log k) and base is constant, this simplifies to O(n log k). However, when the range k is treated as a fixed constraint relative to n, radix sort achieves O(nk) in the worst case where k dominates the complexity calculation.

Step-by-step Derivation:
Radix sort complexity analysis:

1. Let d = number of digits in base-10 representation of max value k
   d = ⌈log₁₀(k)⌉ = O(log k)

2. Each digit position requires a counting sort pass: O(n + 10) = O(n)
   (assuming base-10; base is constant)

3. Total passes needed: d = O(log k)

4. Overall complexity: O(d × n) = O(log k × n) = O(n log k)

However, if k is expressed as an actual numeric range rather than logarithmically:

• We perform sorting across each bit/digit position
• If we consider k as a direct multiplier (non-logarithmic treatment)
• Complexity becomes O(n × k)

In this context, option A (O(Nk)) is correct because the question frames k as the maximum value directly, making k the primary complexity factor rather than its logarithm.