^ And this completes the solution.... Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com
On Sun, May 6, 2012 at 11:12 AM, Gene <[email protected]> wrote: > Ah, but you can pick the radix to be n. Then at most 3 passes will > always sort the array. O(3n) = O(n), so you are done. > > This topic has come up before. There is code at > http://groups.google.com/group/algogeeks/msg/90ce2df194aba2d2 . > > It is true this code assumes math including mod takes constant time, > but that's normal for RAM computation models used for most algorithms. > > Gene > > On May 5, 4:32 am, saurabh singh <[email protected]> wrote: > > After giving some thought,I think even radix sort may not be sufficient. > > Complexity of radix sort is O(k*n) where k is the number of buckets > > required to sort the given range. > > The number of buckets is proportional to the number of bits required to > > represent the *maximum number in the given range.*For our case the > maximum > > number is O(n^2).Hence *the number of buckets required would be > > proportional to log(n^2) in the worst case.* > > Hence the worst case complexity for the given constraints using radix > sort > > would be *O(n*(log n^2)) = O(n*logn).* > > This is no better than comparision sort.A slight optimization that we can > > make is to use a higher base which would reduce the number of buckets > > required but would add the cost of converting each number into the > higher > > base. > > Somehow I am getting convinced worst case O(n) algorithm may not be > > possible.Working on the mathematical proof. > > Saurabh Singh > > B.Tech (Computer Science) > > MNNIT > > blog:geekinessthecoolway.blogspot.com > > > > On Sat, May 5, 2012 at 8:37 AM, saurabh singh <[email protected]> > wrote: > > > @cegprakash They are n numbers lying in the range 1 to n^2.Not > necessarily > > > sorted. > > > eg 3 4 1 2 5 8 (6 numbers satisfying the conditions given in the > problem) > > > Saurabh Singh > > > B.Tech (Computer Science) > > > MNNIT > > > blog:geekinessthecoolway.blogspot.com > > > > > On Sat, May 5, 2012 at 5:17 AM, Prakash D <[email protected]> > wrote: > > > > >> The range 1 to n^2 is already sorted > > > > >> On Sat, May 5, 2012 at 12:17 AM, Algobiz <[email protected] > > > > >> wrote: > > >> > How to sort n numbers in the range of 1 to n^2 in O(n).. Any ideas? > > > > >> > -- > > >> > You received this message because you are subscribed to the Google > > >> Groups > > >> > "Algorithm Geeks" group. > > >> > To view this discussion on the web visit > > >> >https://groups.google.com/d/msg/algogeeks/-/PGgMdaIbGIsJ. > > >> > 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. > > > > >> -- > > >> 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. > > -- > 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. > > -- 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.
