Please Explain also..

Question

. Assume an array A[1….n] has n-elements, and every element of an array is less than or equal to n. An element is said to be majority element, if it occurred in more than n/2 positions of an array. What is the best time complexity to check whether the majority of elements exist or not?

(a) O (log n)                                                                (b) O (n)

(c) O (n log n)                                                             (d) O (n2)

Comments

B is correct.

---

Here every Element is less than equal to n So, make an Array of size n And count the occurrences of each of the element. That will take O(n).

---

https://www.geeksforgeeks.org/majority-element/

Answer 1

It's a kind of application of count sort. Every element of the array is less than or equal to n (i.e. the elements lie in some given range).

We just need first part of the count sort which counts the occurrences of each element.

      A[ ] is the input array, count[ ] keeps track of the number of times each element of A[] occurs

          for i=1 to A.length

          {  count[A[i]]= count[A[i]] + 1  }

   This loop takes O(n) time.

After this we need one more O(n) scan of count[ ] to check if any entry is more than n/2.

Total time complexity= O(n) + O(n)= O(n).  So, answer is (b).