Consider the problem of finding the majority element of an array. $($Leetcode question $169)$ I.e$.$ given, say, the array A $=[$a$,$b$,$c$,$a$,$c$,$a$,$a$],$ the majority element is the character a$.($To clarify, the majority element is not something which occurs $$the most$-$ that would be a plurality. By majority, we mean an element which occurs in more than half of the array.$)$ An array need not have a majority element at all. In this case, we will return $1.$

$($a$)$ Write a brute$-$force python function for calculating and returning the majority element. Note that the elements of A are not assumed to be numbers $-$ they could be anything at all. Your brute$-$force solution should not use dictionaries $-$ arrays only. $($We$$ll come back to this question when we$$ve introduced hash tables in a little bit$).$ What is the runtime?

$($b$)$ Create a divide and conquer algorithm for calculating and returning the majority element in time O$($nlog$($n$)).$ Explain in writing how and why your algorithm works. Justify using the master theorem that this is the runtime, and then create a compare with theory$($algo$,$ theo$)$ function similar to what you used in assignment $2$ in order to demonstrate it empirically. $($Hint: Split the array into two halves. If A has a majority element, how does that element relate to the two halves? Another tip: Use the master theorem to compute how much computation time you can afford per level of recursion.$)$

$($c$)$ If your algorithm relies on a claim relating majority elements of sets to majority elements of their subsets, then you must prove that claim using induction on the size of the set.