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<javascript:_e({}, 'cvml',
> 'algogeeks@googlegroups.com');>
> .
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com <javascript:_e({}, 'cvml',
> 'algogeeks%2bunsubscr...@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.
