Yes..i agree with Dave..Here is what i think. As you have integers upto n^3 in your input, it would need [3*lg(n) + 1] bits to represent each integer. So take each group of r = ceil(lg(n)) bits at a time. So this becomes number of bits needed to represent single digit. Each digit thus can take 2^r values. If you use counting sort to sort digits, it will take O(n+ 2^r ) time.
You have 3 such groups. So 3 passes needed to sort whole input set. Overall complexity is 3*O(n+2^r).... Correct me if i am wrong anywhere in the analysis. -- 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.
