count sort in reverse order would help i guess :) On Sat, Sep 3, 2011 at 11:49 PM, mohit verma <mohit89m...@gmail.com> wrote:
> 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 <mohit89m...@gmail.com>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 < >> thefourrup...@gmail.com> 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 algogeeks@googlegroups.com. >>> To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com. >>> 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 algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- *Dheeraj Sharma* Comp Engg. NIT Kurukshetra +91 8950264227 -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
