In classifying butterflies of several species, a biologist makes time-consuming comparisons between butterfly features to determine whether or not two butterflies are the same species. A biologist wants to determine as efficiently as possible whether or not there is a dominant species among n butterfly specimens, B = (b1, . . . , bn). (A dominant species is one that occurs strictly more than n/2 times in the list of specimens.)

1. Describe a divide and conquer algorithm Dominant(B, n) to tell the biologist how to do this in O(n log n) applications of operation Same(b, b) which returns true if b and b are the same species and false otherwise.
2. Explain why your solution is correct.
3. Write the recurrence that justifies your claim for the O(n log n) running time.