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 <saurab...@gmail.com> 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 <cegprak...@gmail.com> wrote: > >> The range 1 to n^2 is already sorted >> >> On Sat, May 5, 2012 at 12:17 AM, Algobiz <deepak.arulkan...@gmail.com> >> 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 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. >> >> -- >> 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. >> >> > -- 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.
