Practical efficiency? If you want to print out n^2 things then you can't do
it in less than n^2.
If you can come up with an encoding that represents more than one inversion
then great.
However, that doesn't change the fact that you can't individually print out
n^2 things in under n^2 time.
Look up
@carl barbon
if in worst case to print all inversion it takes O(n^2) why to use merge
sort ot BIT , simply use insertion sort ..
On Wed, Oct 24, 2012 at 12:03 AM, Dipit Grover wrote:
> ^ Exactly!
>
> Dipit Grover
> B.Tech in Computer Science and Engineering - lVth year
> IIT Roorkee, India
>
>
>
^ Exactly!
Dipit Grover
B.Tech in Computer Science and Engineering - lVth year
IIT Roorkee, India
--
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
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
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 th
