Time and space complexity of Radix sort

Question

I had previously asked a question on space complexity of radix sort here. I have also read this question. However, I still get confused about it which means that the concept is not clear. I have the following implementation which is meant only for positive integers:

#include <iostream>
#include <vector>
#include <array>
#include <string>
#include <sstream>
#include <algorithm>

void radix_sort(std::vector<int>& arr)
{
    int rad = 1;
    int max_val = *(std::max_element(arr.begin(), arr.end()));
    while(max_val / rad)
    {
        std::array<std::vector<int>, 10> buckets;
        int n = arr.size();
        for(int i = 0; i < n; i++)
        {
            buckets[arr[i] / rad % 10].push_back(arr[i]);
        }

        auto k = arr.begin();
        for(auto b : buckets)
        {
            k = std::copy(b.begin(), b.end(), k);
        }

        rad *= 10;
    }
}

void print_array(std::vector<int>& arr)
{
    for(auto num : arr)
    {
        std::cout << num << "\t";
    }
    std::cout << "\n";
}


int main()
{
    int val;
    std::vector<int> arr;
    std::string s;
    std::cout << "Enter the numbers in the array: \n";
    std::getline(std::cin, s);
    std::istringstream ss{s};
    while(ss >> val)
    {
        if(val != ' ')
        {
            arr.push_back(val);
        }

    }
    std::cout << "Before sorting: \n";
    print_array(arr);
    radix_sort(arr);
    std::cout << "After sorting: \n";
    print_array(arr);
    return 0;
}

The time complexity is O(kn) and space complexity is O(k + n). Here n is the number of elements and k is the number of bits required to represent largest element in the array. My problem is with k and I am not able to understand how that effects the complexity. In the above code the number of times the outermost while loop runs depends on the number of digits of maximum value. Until recently I assumed that k represented this number of digits of maximum value. However, that is not the case. Can anyone please explain in simpler terms?

Edit: Pseudocode

1) Take the array as input

2) Initialize a variable `rad` as 1

3) Find maximum value element in the array

4) Until all the digits in maximum value element are visited:

          i) Create buckets for digits from 0 to 9.

          ii) Based on `rad`, calculate digits in a particular place of number (eg: unit's, ten's, hundred's etc.).

          iii) Fill the buckets with elements, based on the digit they have in the place under consideration in the loop. 

          iv) Take out the numbers from buckets in the order bucket0 to bucket9 and use it to populate the original array.

          v) Update `rad` to change the place under consideration for the next loop.

Answer 1

A

$k$ represented this number of digits of maximum value.

B

k is the number of bits required to represent largest element in the array

This translates to number of digits required to represent the max value in binary.

A is equivalent to B.

Here is how:

Say largest element in the array is 1233.

According to B, $k = log_2(1233) \approx 11$

According to A, $k = 4$, which is just $log_{10}(1233)$.

There is formula for converting between the $$log_a(n) = \frac{log_b(n)}{log_b(a)}.$$

The denominator here $log_a(b)$ is a constant.

So $log_2(n) = O(log_{10}(n))$. So it doesn't really matter to radix sort what base you are using.

Answer 2

Another way to think about $k$ is to express the range of numbers in terms of $n$.

If you think this way, the usual radix sort algorithm sorts $n$ integers in the range $[1,n^c]$ in $O(cn)$ time using $O(n)$ words of extra space. The parameter $c$ doesn't enter into the space complexity analysis because it measures the number of radix passes.