title: Why does radix sort have a space complexity of O(k + n)?
body: <p>Consider an array with <code>n</code> numbers that has maximum <code>k</code> digits (See Edit). Consider the radix sort program from <a href="http://www.geekviewpoint.com/python/sorting/radixsort" rel="noreferrer">here</a>:</p>
  
  <pre><code>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 &gt; 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
  </code></pre>
  
  <p>The <code>buckets</code> basically is a 2d list of all the numbers. However, only <code>n</code> values will be added to it. How come the space complexity is O(k + n) and not O(n)? Correct me if I am wrong, even if we consider the space used to extract digits in a particular place, it is only using 1 (constant) memory space?</p>
  
  <p><strong>Edit</strong>: I would like to explain my understanding of <code>k</code>. Suppose I give an input of <code>[12, 13, 65, 32, 789, 1, 3]</code>, the algorithm given in the link would go through 4 passes (of first <code>while</code> loop inside the function). Here <code>k</code> = 4, i.e. maximum no. of digits for any element in the array + 1. Thus k is no. of passes. This is the same <code>k</code> involved in time complexity of this algorithm: <code>O(kn)</code> which makes sense. I am not able to understand how it plays a role in space complexity: <code>O(k + n)</code>. </p>