Re: [algogeeks] Re: Sorting in O(n)
Read the problem for constraints Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com On Tue, May 8, 2012 at 11:12 AM, Mahesh Thakur wrote: > I think if range is till n2, max passes for radix sort will be 3. > by subtracting 1 to all the numbers we get the max range to n2-1 and radix > sort can be done in 2 passes. > but what will happen when if we have a '0' in array and then we subtract 1 > to it? > > > On Tue, May 8, 2012 at 9:48 AM, atul anand wrote: > >> @arpit : why algo subtracts 1 from each number of the input? >> >> On Sun, May 6, 2012 at 12:02 AM, Arpit Gupta > > wrote: >> >>> 1) Substract 1 from each no. >>> 2) Now after substracting 1 from each no, convert it to base n. >>> for example for n=6,the number 36 will be converted to 55. (36-1=35 >>> and 35 when converted to base 6 is 55) >>> 3) Thus all the nos in the range 1 to 6^2 can be mapped to numbers >>> between 00 to 55. >>> 4) Now apply radix sort(for two digits) for the mapped values. >>> 5)After sorting the mapped values convert base n values to decimal and >>> add 1. >>> >>> This is o(n) algo. >>> PS: I am not the designer of this algo. One of my seniors told me. >>> >>> >>> On Sat, May 5, 2012 at 2:42 PM, saurabh singh wrote: >>> 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 >>> > 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 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 >> 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, Prak
Re: [algogeeks] Re: Sorting in O(n)
I think if range is till n2, max passes for radix sort will be 3. by subtracting 1 to all the numbers we get the max range to n2-1 and radix sort can be done in 2 passes. but what will happen when if we have a '0' in array and then we subtract 1 to it? On Tue, May 8, 2012 at 9:48 AM, atul anand wrote: > @arpit : why algo subtracts 1 from each number of the input? > > On Sun, May 6, 2012 at 12:02 AM, Arpit Gupta > wrote: > >> 1) Substract 1 from each no. >> 2) Now after substracting 1 from each no, convert it to base n. >> for example for n=6,the number 36 will be converted to 55. (36-1=35 and >> 35 when converted to base 6 is 55) >> 3) Thus all the nos in the range 1 to 6^2 can be mapped to numbers >> between 00 to 55. >> 4) Now apply radix sort(for two digits) for the mapped values. >> 5)After sorting the mapped values convert base n values to decimal and >> add 1. >> >> This is o(n) algo. >> PS: I am not the designer of this algo. One of my seniors told me. >> >> >> On Sat, May 5, 2012 at 2:42 PM, saurabh singh wrote: >> >>> 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 >>> 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 >>> > 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 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 > 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 > 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 > 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 > Goo
Re: [algogeeks] Re: Sorting in O(n)
what he wanted to say was that first digit would be m/n and second digit m%n Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com On Tue, May 8, 2012 at 10:31 AM, atul anand wrote: > @arpit : your formula for converting base 10 to base n is bit wrong , > right formula should be :- > > > let given base 10 no is m and we need to convert it in base n. > then base n converted no is ( (m/n) * 10) + (m%n) ie 34 base 10 in base 6 > is ((34/6)*10) + (34%6) ie 54 > > > On Sun, May 6, 2012 at 10:20 PM, Arpit Gupta > wrote: > >> O(1) base conversion can here be done as follows:-(works only when >> numbers are in range 0 to n^2-1) >> *From base 10 to base n >> *let given base 10 no is m and we need to convert it in base n. >> then base n converted no is (m/n)(m%n) ie 34 base 10 in base 6 is >> (34/6)(34%6) ie 54 >> >> Now i think you can yourself write base n to base 10 conversion. >> >> >> On Sun, May 6, 2012 at 11:13 AM, saurabh singh wrote: >> >>> ^ 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 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 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 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 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. >>> -- >>> You received this message because you are subscribed to the Google >>
Re: [algogeeks] Re: Sorting in O(n)
@arpit : your formula for converting base 10 to base n is bit wrong , right formula should be :- let given base 10 no is m and we need to convert it in base n. then base n converted no is ( (m/n) * 10) + (m%n) ie 34 base 10 in base 6 is ((34/6)*10) + (34%6) ie 54 On Sun, May 6, 2012 at 10:20 PM, Arpit Gupta wrote: > O(1) base conversion can here be done as follows:-(works only when numbers > are in range 0 to n^2-1) > *From base 10 to base n > *let given base 10 no is m and we need to convert it in base n. > then base n converted no is (m/n)(m%n) ie 34 base 10 in base 6 is > (34/6)(34%6) ie 54 > > Now i think you can yourself write base n to base 10 conversion. > > > On Sun, May 6, 2012 at 11:13 AM, saurabh singh wrote: > >> ^ 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 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 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 >>> 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 >>> 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. >>> >>> >> -- >> 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. >> > > > > -- > Arpit Gupta > B.Tech Third Year > Computer Science And Engineeri
Re: [algogeeks] Re: Sorting in O(n)
@arpit : why algo subtracts 1 from each number of the input? On Sun, May 6, 2012 at 12:02 AM, Arpit Gupta wrote: > 1) Substract 1 from each no. > 2) Now after substracting 1 from each no, convert it to base n. > for example for n=6,the number 36 will be converted to 55. (36-1=35 and > 35 when converted to base 6 is 55) > 3) Thus all the nos in the range 1 to 6^2 can be mapped to numbers between > 00 to 55. > 4) Now apply radix sort(for two digits) for the mapped values. > 5)After sorting the mapped values convert base n values to decimal and add > 1. > > This is o(n) algo. > PS: I am not the designer of this algo. One of my seniors told me. > > > On Sat, May 5, 2012 at 2:42 PM, saurabh singh wrote: > >> 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 >> 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 >>> 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 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 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 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 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:
Re: [algogeeks] Re: Sorting in O(n)
Yes thanx for that...Gene had already mentioned that in somewhat different way.And now I feel like a floppy disk for not being able to think the obvious. Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com On Sun, May 6, 2012 at 10:20 PM, Arpit Gupta wrote: > O(1) base conversion can here be done as follows:-(works only when numbers > are in range 0 to n^2-1) > *From base 10 to base n > *let given base 10 no is m and we need to convert it in base n. > then base n converted no is (m/n)(m%n) ie 34 base 10 in base 6 is > (34/6)(34%6) ie 54 > > Now i think you can yourself write base n to base 10 conversion. > > > On Sun, May 6, 2012 at 11:13 AM, saurabh singh wrote: > >> ^ 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 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 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 >>> 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 >>> 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. >>> >>> >> -- >> 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. >> > > > > -- > Arpit Gupta > B.Tech Third Year > Computer Science And Engineering > M.N.N.I.T Allahabad >
Re: [algogeeks] Re: Sorting in O(n)
O(1) base conversion can here be done as follows:-(works only when numbers are in range 0 to n^2-1) *From base 10 to base n *let given base 10 no is m and we need to convert it in base n. then base n converted no is (m/n)(m%n) ie 34 base 10 in base 6 is (34/6)(34%6) ie 54 Now i think you can yourself write base n to base 10 conversion. On Sun, May 6, 2012 at 11:13 AM, saurabh singh wrote: > ^ 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 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 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 >> 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 >> 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. >> >> > -- > 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. > -- Arpit Gupta B.Tech Third Year Computer Science And Engineering M.N.N.I.T Allahabad arpitgupta.211...@gmail.com -- 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.
Re: [algogeeks] Re: Sorting in O(n)
^ 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 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 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 > 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 > wrote: > > > > >> The range 1 to n^2 is already sorted > > > > >> On Sat, May 5, 2012 at 12:17 AM, Algobiz > > > >> 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. > > -- 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.
[algogeeks] Re: Sorting in O(n)
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 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 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 wrote: > > >> The range 1 to n^2 is already sorted > > >> On Sat, May 5, 2012 at 12:17 AM, Algobiz > >> 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.
Re: [algogeeks] Re: Sorting in O(n)
^ This is what I was talking about in my earlier post.But the problem is how\ to convert the base of each number in O(1) time ( and then reconvert to base 10 in O(n)) .I may be missing some trick here.Still working on it. Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com On Sun, May 6, 2012 at 12:02 AM, Arpit Gupta wrote: > 1) Substract 1 from each no. > 2) Now after substracting 1 from each no, convert it to base n. > for example for n=6,the number 36 will be converted to 55. (36-1=35 and > 35 when converted to base 6 is 55) > 3) Thus all the nos in the range 1 to 6^2 can be mapped to numbers between > 00 to 55. > 4) Now apply radix sort(for two digits) for the mapped values. > 5)After sorting the mapped values convert base n values to decimal and add > 1. > > This is o(n) algo. > PS: I am not the designer of this algo. One of my seniors told me. > > > On Sat, May 5, 2012 at 2:42 PM, saurabh singh wrote: > >> 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 >> 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 >>> 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 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 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 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 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
Re: [algogeeks] Re: Sorting in O(n)
1) Substract 1 from each no. 2) Now after substracting 1 from each no, convert it to base n. for example for n=6,the number 36 will be converted to 55. (36-1=35 and 35 when converted to base 6 is 55) 3) Thus all the nos in the range 1 to 6^2 can be mapped to numbers between 00 to 55. 4) Now apply radix sort(for two digits) for the mapped values. 5)After sorting the mapped values convert base n values to decimal and add 1. This is o(n) algo. PS: I am not the designer of this algo. One of my seniors told me. On Sat, May 5, 2012 at 2:42 PM, saurabh singh wrote: > 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 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 >> 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 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 >>> 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 >>> 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 >>> 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 t
Re: [algogeeks] Re: Sorting in O(n)
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 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 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 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 >> 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 >> 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 >> 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
Re: [algogeeks] Re: Sorting in O(n)
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 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 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 > 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 > 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 > 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 t
[algogeeks] Re: Sorting in O(n)
@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 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 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 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 wrote: > > >>> The range 1 to n^2 is already sorted > > >>> On Sat, May 5, 2012 at 12:17 AM, Algobiz > >>> 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.
[algogeeks] Re: Sorting in O(n)
You can use Radix Sort. It will have a Time Complexity of O(n). On Saturday, May 5, 2012 12:17:15 AM UTC+5:30, Algobiz 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/-/OLTTwzx8f9MJ. 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.
