Linda creates an algorithm that takes an input sequence S and produces an output sequence T that is a sorting of the n elements of S.
a) Give an algorithm, isSorted, for testing in O(n) time if T is sorted.
b) Explain why the algorithm isSorted is not sufficient to prove a particular output T of Linda's algorithm is a sorting of S.
c) Describe what additional information Linda's algorithm could output so that her algorithm's correctness could be established on any given S and T in O(n) time.