Радикальная сортировка (реализация Java) сложность

Question

Это мой первый вопрос, поэтому я надеюсь, что не нарушил никаких правил. Мне наконец-то удалось написать код для алгоритма сортировки по Radix, но мне интересно, сделал ли я это неправильно. Что заставляет меня думать, что мой алгоритм выглядит сложным O(n^3), но Radix Sort, как известно, является алгоритмом O(kn). Я неправильно вычисляю сложность моего алгоритма или я просто написал действительно плохой код?

private static void radixSort(int[] A){
    ArrayList<Integer>[] bucket = new ArrayList[10];
    int maxNumberOfDigits = 0;
    for(int number : A){
        if(numberOfDigitsIn(number) > maxNumberOfDigits) maxNumberOfDigits = numberOfDigitsIn(number);
    }
    for(int c=0; c<bucket.length; c++){
        bucket[c] = new ArrayList<Integer>();
    }
    int i = 0;
    int digit;
    int j;
    while(i < maxNumberOfDigits){
        for(j = 0; j<A.length; j++){
            digit = getDigit(A[j], i);
            bucket[digit].add(A[j]);
        }

        int index = 0;
        for(int z = 0; z<bucket.length; z++){
            for (int k=0; k<bucket[z].size(); k++){
                A[index] = bucket[z].get(k);
                index += 1;

            }
            bucket[z].clear();
        }
        i += 1;
    }
}

Методы getDigit() и numberOfDigitsIn() имеют постоянное время.

Answer 1

    for(int z = 0; z<bucket.length; z++){
        for (int k=0; k<bucket[z].size(); k++){

Ключевым моментом здесь является то, что общая сумма всех размеров сегмента будет равна n, поэтому эти объединенные циклы принимают только O(n). Цикл над j занимает O (n), а цикл while на i будет выполняться для итераций maxNumberOfDigits, и это число представляет k в описанной вами среде выполнения O(kn). Таким образом, общее количество фактически равно O(kn).