Why is radix sorting of spatial complexity O (k + n)?

Question

Consider an array with numbers n that has maximal digits k (see the "Editing" section). Consider the radix collation program from here :

 def radixsort( aList ): RADIX = 10 maxLength = False tmp, placement = -1, 1 while not maxLength: maxLength = True # declare and initialize buckets buckets = [list() for _ in range( RADIX )] # split aList between lists for i in aList: tmp = i / placement buckets[tmp % RADIX].append( i ) if maxLength and tmp > 0: maxLength = False # empty lists into aList array a = 0 for b in range( RADIX ): buck = buckets[b] for i in buck: aList[a] = i a += 1 # move to next digit placement *= RADIX 

buckets is basically a 2nd list of all numbers. However, only n values ​​will be added to it. What is the complexity of the space O (k + n), not O (n)? Correct me if I am wrong, even if we look at the space used to extract numbers in a specific place, it uses only 1 (constant) memory space?

Change I would like to explain my understanding of k . Suppose I give the input [12, 13, 65, 32, 789, 1, 3] , the algorithm specified in the link will go through 4 passes (of the first while inside the function). Here k = 4, i.e. Maximum No. digits for any element of the array + 1. Thus, k is not. passageways. This is the same k involved in the time complexity of this algorithm: O(kn) , which makes sense. I cannot understand how it plays a role in cosmic complexity: O(k + n) .

Answer 1

The complexity of Radix spatial sorting is tied to the sorting that it uses to sort each element. At best, this is a sort count.

Here is the pseudo code provided by CLRS for counting sorting:

 Counting-sort(A,B,k) let C[0..k] be a new array for i = 0 to k C[i] = o for j = 1 to A.length C[A[j]] = C[A[j]] + 1 for i = 1 to k C[i] = C[i] + C[i-1] for j = A.length down to 1 B[C[A[j]]] = A[j] C[A[j]] = C[A[j]] - 1 

As you can see, sorting count creates several arrays, one based on size K, and one based on size N. B is an output array of size n. C is an auxiliary array of size k.

Since radix sorting uses counting sorting, counting the complexity of the sorting space is the lower bound on the complexity of the sorting space of the numbering.

Answer 2

I think there is a terminological problem. The spatial complexity of the implementation and implementation of the question, mentioned in the Jayson Boubin answer , is O(n+k) . But k not the length of the longest word (or the longest number). k is the size of the "alphabet": the number of different numbers (in numbers) or letters (in words).

buckets = [list() for _ in range( RADIX )]

This code creates an array with RADIX elements. There is a constant in this particular RADIX implementation (and the spatial complexity is O (n)), but in general it is a variable. RADIX is k , the number of different digits (letters in the alphabet). And this k does not depend on n and can be more than n in some cases, therefore the complexity of the space O (n + k) in the general case.

Change In this, an implementation with a size of placement (or tmp ) is O(k) (with your definition of k ), because k is log(maxNumber) base 10 , and placement size of log(maxNumber) base 256 . But I'm not sure if this is a common case.

Answer 3

To sort Radix, a counting sort is used for each digit of the numbers in the data set. Sorting sorting has spatial complexity O (n + k), where k is the largest number in the data set.

Decimal digits range from 0 to 9, so if we sort 4 decimal numbers (11,22,88,99) using radix sort (sort sort used in radix sort), an array of size b = 10 will be created for each digit, where b is the base.

This means that the total used space will be the full number * (n + base). If the total number is constant. The complexity of the space becomes O (n + base).

Therefore, the spatial complexity of the Radix Sort is O (n + b).