title: Runtime for Assignment Part of Radix Sort
body: <p>How would you describe the runtime analysis of the following bit of code? It is the second step in radix sort (first step is creating the counter).</p>
  <pre><code>   const reAssignArraySlots = (arr, counter) =&gt; {
        let i = 0;
        let j = 0;
        while(i&lt;arr.length) {
          let k = 0;
          let num = counter[i] || 0;
          while(k&lt;num) {
            arr[j] = i;
            k+=1;
            j+=1;
          }
          i+=1;
          j+=1;
        }
        return arr;
      };
  </code></pre>
  <p>I believe it would be O(n) no matter what, but wanted to check that intuition. Examples:</p>
  <p>A) All the elements are the same. The counter would be { '2': 3 }. The while loop with i would process 1x, the while loop with k would process 3x, and each insertion would be O(1). I add up the 3 insertions to make O(3) which is O(n)</p>
  <p>B) All the elements are unique. The counter would be { '2': 1, '1': 1, '3': 1 }. The while loop would process i 3x. Each insertion would be O(1) which would add up to O(3) which is O(n).</p>
  <p>C) Non-unique, non-sequential elements. { '4': 1, '1': 1, '3': 2 }. Here I am unsure. We'd have O(1) for each insertion, but we'd have an additional check for i = 2, which isn't in here. Not sure if that bumps us up to O(4). Eventually if we had something sparse enough, this could get O(n^2).</p>
  <p>Rest of the Code:</p>
  <pre><code>    const getCounter = (arr) =&gt; {
    const counter = {};
    let min, max;
    arr.forEach((item) =&gt; {
      if(counter[item] !== undefined) {
        counter[item] += 1;
      } else {
        counter[item] = 1;
      }
    });
    return counter;
  };
  
  export const countSort = (arr) =&gt; {
    const counter = getCounter(arr);
    return reAssignArraySlots(arr, counter);
  };
  </code></pre>