Problem
You constantly receive Instagram images of your friends' favorite pets, right? (dog, cat, fish, octapus, ...) Enough! You want to determine biases in your social circle; perhaps your views are being skewed because you hang around too many cat lovers. A notoriously difficult task in machine vision is to classify images. So, to analyze your Instagram feed, you can use a captcha-style system: you can submit two images, and the captcha-Human-Turing test will tell you whether the two images are the same pet or not. Each such query is very expensive. Given a set of n input images, (i1, i2, . . ., in), can you determine if more than half of your social network has the same favorite pet using only Q(n) queries? Describe your (divide and conquer) algorithm; analyze its running time. (You should get a Θ(n) runtime)