made easy

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 is occured in more than n/2 positions of an array.What is the time complexity to check whether the majority element exist or not in the given array?[Best answer]

a)O(logn)                                      b)O(n)

c)O(nlogn)                                    d)O(n^2)

Comments

If it is unsorted array then O(n)  and if sorted then O(logn)

Answer 1

b)O(n). Because nothing given about sorting.

Comments

can you explain how it is O(n)