17. A majority tree is a complete binary tree with depth n, where every leaf is labeled either 0 or 1. The value of a leaf is its label; the value of any internal node is the majority of the majority tree, given the sequence of 3n leaf labels as input. For example, if n = 2 and the leaves are labeled 1,0,0,0, 1,0,1,1,1, the root has value 0 A majority tree with depth n 2. (a) Prove that any deterministic algorithm that computes the value of the root of a majority (b) Describe and analyze a randomized algorithm that computes the value of the root in tree must examine every leaf. [Hint: Consider the special case n-1. Recurse.] worst-case expected time O(cn) for some constant c