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();
        }
    }
}
```

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();
        }
    }
}

No comments on the code. But 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.

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();
        }
    }
}
```