0 votes 0 votes 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. Programming in C data-structures + – akankshadewangan24 asked Dec 2, 2017 akankshadewangan24 265 views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply joshi_nitish commented Dec 2, 2017 reply Follow Share 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) 0 votes 0 votes Ashwin Kulkarni commented Dec 2, 2017 reply Follow Share 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) 0 votes 0 votes srivivek95 commented Dec 2, 2017 reply Follow Share 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 1 votes 1 votes Please log in or register to add a comment.
