That statement is only very superficially similar. Counting them is saying how many of them there are, it doesn't necessarily require you to look at/compute each one. So it is not the same as printing them.
If you're saying I want to print out each inversion individually then it's going to be n^2 and there's no way around it. If you have some other encoding so you can print something which represents multiple inversions in 1 step, you might be able to get under n^2. On 22 October 2012 12:03, Aamir Khan <syst3m.w...@gmail.com> wrote: > > > On Monday, October 22, 2012, Dipit Grover wrote: > >> Since the number of inversions are of order n^2 in the worst case, so >> should be the complexity of printing them apparently. > > > It makes sense to some extent but this is no proof. There has to be a > better proof for lower bound of complexity for this algorithm. Because I > can state similar statement, > > "Since the number of inversions are of order N^2 in the worst case, so > should be the complexity of counting them apparently". > > But we all know this is not true as we already know O(nlogn) solution. > > >> -- >> 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. >> > > > -- > > Aamir Khan | 4th Year | Computer Science & Engineering | IIT Roorkee > > > -- > 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.
