The first observation in the lower bound for comparison-based sorting is that any comparison-based sorting algorithm with a fixed-size input can be turned into an equivalent decision tree.

Now consider comparison based sorting algorithm:

1. Draw the decision tree that shows Selection-Sorts behavior on inputs of size 3.
2. Based on this decision tree, what are the minimum and maximum number of comparisons performed by Selection-Sort on an input of size 3?
3. What can you conclude from the last two parts about the average number of comparisons made by Selection-Sort vs the average number of comparisons made by Insertion-Sort, on random inputs of size 3?

Selection-Sort(A) for i = 1 to A.length-1 minp = i for j =i+1 to A.length if A[j]