Consider the radix sort algorithm.

(i) Explain how radix sort works, to what inputs it can be applied and what its asymptotic complexity is. [5 marks]

(ii) Explain why running radix sort does not proceed from most to least significant digit, as would at first seem more intuitive. [4 marks]

(iii) Give a proof by induction of the correctness of radix sort. [4 marks]

(b) Clearly describe an algorithm, strictly better than O(n 2 ), that takes a positive integer s and a set A of n positive integers and returns a Boolean answer to the question whether there exist two distinct elements of A whose sum is exactly s. Evaluate its complexity. [7 marks]