0
\$\begingroup\$

I read time complexity of radix sort is O(wn) or O(n log n), if all n numbers are distinct. After implementation it look to me as if I have implemented radix sort which has time complexity of O(n ^2). Please take a look at my implementation and suggest, if there is some implementation problem or my observation about time complexity is wrong.

Please note: I have hard coded few values for simplicity to sort 3 digit numbers only.

private void LSBSort(int[] arr) {
    _LSBSort(arr, 1);
}

private void _LSBSort(int[] arr, int divisor) {
    Deque[] deques = new Deque[10];
    for(int i = 0 ; i < arr.length ; i++) {
        int mod = (arr[i] /divisor ) % 10;
        if (deques[mod] == null) {
            deques[mod] = new ArrayDeque<>();
        }
        deques[mod].add(arr[i]);
    }
    divisor *= 10;
    if (divisor > 1000) {
        return;
    }

    int cursor = 0;
    for (int i = 0 ; i < 10 ; i++) {
        if (deques[i] != null) {
            for (int j = 0 ; j <= deques[i].size() ; j++) {
                cursor = cursor + j;
                arr[cursor] = (int)deques[i].pollFirst();
            }
            cursor++;
        }
    }
    _LSBSort(arr, divisor);
}
\$\endgroup\$
  • \$\begingroup\$ Why do you think the time complexity is O(n^2)? To me, it looks like each run of _LSBSort takes time O(n), and it is repeated w times. \$\endgroup\$ – Benjamin Kuykendall Mar 11 at 22:07
  • \$\begingroup\$ Due to nested for loop in _LSBSort and if every deque is not null it will take O(n^2) time. \$\endgroup\$ – Balkrishan Nagpal Mar 12 at 0:41
  • \$\begingroup\$ Remember that each item in the list is in exactly one of the deques -- thus iterating through all 10 deques is only iterating through n objects in total. \$\endgroup\$ – Benjamin Kuykendall Mar 12 at 0:47
  • \$\begingroup\$ but one qeque can have more than one element and iterating each deque is proportional to its size. \$\endgroup\$ – Balkrishan Nagpal Mar 12 at 2:38
  • 2
    \$\begingroup\$ Precisely. Say deques[i] contains si items, so iterating over it takes time O(si). Then the outer for loop takes time O(s1) + O(s2) ... + O(s10) = O(s1 + s2 + ... + s10). But since each item occurs in exactly one deque, we know s1 + s2 + ... + s10 = n. Conclude the loop takes time O(n). \$\endgroup\$ – Benjamin Kuykendall Mar 12 at 4:09
1
\$\begingroup\$

First: the runtime is O(wn), as it should be for this algorithm.

Consider a single run of _LSBSort. Let n be the length of arr. Clearly the first loop is time O(n). Let si be the length of deques[i]. Then the second loop is time $$ O(s_1) + O(s_2) + \dots + O(s_{10}) = O(s_1 + s_2 + \dots + s_{10}).$$ Noting that each element is present in exactly one of the deques, we conclude $$s_1 + s_2 + \dots + s_{10} = n.$$ Thus the entire method runs in time O(n). As it is called w times, we conclude the entire algorithm is O(wn) time.

Second: some comments on the code.

  1. These methods should be static.
  2. Use an ArrayList for deque. Arrays of generics are just too ugly.
  3. Call the list deques because it is plural.
  4. Initialize all the deques up front. Clear and reuse between iterations.
  5. Use extended for loops throughout.
  6. Use loop instead of recursion.
private static void LSBSort(int[] arr) {
    List<ArrayDeque<Integer>> deques = new ArrayList<>(10);
    for (int i = 0; i < 10; i++) {
        deques.add(new ArrayDeque<Integer>());
    }

    for (int d = 1; d <= 1000; d *= 10) {
        for(int i : arr) {
            deques.get((i / d) % 10).add(i);
        }

        int cursor = 0;
        for (Deque<Integer> D : deques) {
            for (Integer j : D) {
                arr[cursor++] = j;
            }

            D.clear();
        }
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.