Ohh my bad. the complexity should be O(nlogn) + O(mlogm) +O(m) = O(tlogt) where t=max(m,n)
On Sat, Sep 3, 2011 at 11:46 PM, mohit verma <[email protected]> wrote: > create a binary search tree by scanning the whole array and if the value > already exists increase count field in that node O(nlogn). Now traverse the > tree in any order by creating another tree with kery - count. O(nlogn). > Doing reverse inorder traversal print value field of each node count number > of times O(n). > > overall complexity - O(nlogn)+O(nlogn)+O(n) = O(nlogn). > > > On Sat, Sep 3, 2011 at 11:16 PM, Siddhartha Banerjee < > [email protected]> wrote: > >> perhaps we can make it O(mlogm), m= no of distinct elements... just create >> a hash table and store the count of the number of time elements occur... >> O(n), now sort the m elements and proceed as above... >> it is obviously not possible to do it faster than O(mlogm), where m = no >> of distinct elements... >> so order = O(n+mlogm)=O(mlogm)(???, assuming m!<<n) >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > > > -- > ........................ > *MOHIT VERMA* > > -- ........................ *MOHIT VERMA* -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
