Data structure

Question

Which of the following statement are true?

1. Computing the most frequently  occurring elements in an array a(1....n) can be done in o(nlogn) time.

Comments

right now, only algorithm sriking in my mind to do so is,

1) sort the array -> O(nlogn)

2) do one single traversal, to find most frequent element -> O(n)

overall, O(nlogn)+O(n) = O(nlogn)

---

If we use counting sort if numbers are fixed then also to get most frequently occurring elements anyhow we've to sort the array hence complexity will be O(nlogn)

---

We can find the minimum & maximum element in the array in O(n) time

If extra space is allowed, we can have a hash table of size = max - min +1 ranging from min to max

Computing frequency of each element from the hash table wil require O(n) time