Let us say that a number x is c-major for an n-element array A, if more than n/c elements of A are equal to x. (a) Give O(n)-time algorithm to find...

1.Let us say that a number x is c-major for an n-element array A, if more than n/c elements of A are equal to x.

(a) Give O(n)-time algorithm to find all 2-major elements of A. How many could there be?

(b) Give O(cn)-time algorithm to find all c-major elements of A. How many could there be?

2.Consider a sorted array A of n elements and two integers x and y not in the array, with x y. A comparison based algorithm computes how many elements in A are less than both x and y, how many elements are between x and y and how many are bigger than both x and y. What is the best lower bound (precise answer, not asymptotic) you can prove (using the decision tree technique) for the time complexity of the algorithm?