I think I couldn't make myself clear... This line in your algorithm "*After this just iterate through the aux array printing the index aux[i] times.*" this makes your algorithm O(n^2) since the size of aux is n^2 and in the worst case the complete traversal of aux may be required.
Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com On Sat, May 5, 2012 at 2:37 PM, Jeevitesh <jeeviteshshekha...@gmail.com>wrote: > Hi Shiva. > > You are right we will be wasting a lot of memory. > But still it depends like if we have lot of numbers in the range of 1, n^2 > present in the input array then this trade off is not bad. > The issue here is we cannot otherwise sort it in O(n) time unless and > until we have extra space. > > So we will have to live with it in this case as i do not think it would be > possible in O(n) time otherwise. > > > On Sat, May 5, 2012 at 2:33 PM, shiv narayan <narayan.shiv...@gmail.com>wrote: > >> @jeevitesh yeah that may be right but it requires extra space as lot >> of space will be wasted... >> >> On May 5, 1:44 pm, Jeevitesh <jeeviteshshekha...@gmail.com> wrote: >> > Hi all, >> > >> > I am new to this group. >> > >> > My last post was deleted i do not know the reason behind it. >> > >> > I will explain my logic here:- >> > >> > as the range is 1 to n^2 we have a input array like input[n^2]. >> > We can take a auxillary array of size n^2 like aux[n^2]. >> > Scan the input array. >> > For each input input[i] increment by one corresponding aux[input[i]]. >> > After this just iterate through the aux array printing the index aux[i] >> > times. >> > >> > This way we can sort it in O(n) time. >> > >> > >> > >> > >> > >> > >> > >> > >> > >> > On Sat, May 5, 2012 at 2:02 PM, saurabh singh <saurab...@gmail.com> >> 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 <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. >> > >> > -- >> > *Thanks, >> > Jeevitesh Shekhar Singh.* >> >> -- >> 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. > -- 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.
