Question

Let’s give a formal proof that RadixSort works and give a bound on its runtime.

We start with correctness:

Lemma RadixSort will properly sort any n natural numbers.
Prove this statement. You can use any strategy you want, but we recommend using induction on l (the number of digits that each value has).

Answer 1

Let's take the proof first , so as recommended we'll use the Induction Principle,

As suggested we'll take the value as the number of digits

P(1) The base case is easy to prove which you can just write

P(n) : Assume that for N numbers the unit/tenth/.. digit total

'n' and we can sort that part (for any N numbers)

P(n+1) : We have 1,2,3,...n+1

using the P(n) we can have 1,2,3...n be sorted easily and 2,3,4...n,n+1 as well, so from this we have 1,2,3..n+1 sorted entirely as well. So for digits at each location.

Therefore the Radix Sort Algorithm works.

Now to get the bound let's say for the N number have 'b' digits in each of then

We sort the 'bth' digits first for all N numbers, now the sorting here since has to be done into 1,2,3..9 only so we go for Counting Sort.

Which has a complexity of (n+k) where n is number of digits and k is the number of range what the counting sort does is it out everyone in one of the k boxes in our cases it's 10. So each sorting is O(n+10) and we have 'b' digits so it's a 'b' digit number so we do sorting for b times this thus total radix sort is

O(b(n+10)) now to consider n>>>>10 we have

O(bn) which is correct but in practice we know that there will.be some 5-50 digit number only so b becomes a constant and Radix Sort is O(n) times a constant.

Complexity thus is Linear.

Hope it helps, if any help needed put in comment