Ohh. Missed out the nlogn condition you mentioned. It will do but in n^2 Sent from my Windows Phone ------------------------------ From: D.N.Vishwakarma@IITR Sent: Thursday, 9 June 2011 4:29 PM To: [email protected] Subject: Re: [algogeeks] Finding total number of inversions in an array in O(nlogn) complexity .
how insertion sort will do in O(nlogn)? On Thu, Jun 9, 2011 at 4:27 PM, Navneet Gupta <[email protected]> wrote: > Insertion sort also would do. > > On Thu, Jun 9, 2011 at 4:22 PM, D.N.Vishwakarma@IITR <[email protected]> > wrote: > > thanx for suggestion > > > > On Thu, Jun 9, 2011 at 4:08 PM, sunny agrawal <[email protected]> > > wrote: > >> > >> Discussed many times, > >> 1) add some lines to merge sort > >> 2) use Binary indexed tree for a faster version (i have not tried but > get > >> to know it can be done using binary indexed tree) > >> > >> On Thu, Jun 9, 2011 at 4:05 PM, D.N.Vishwakarma@IITR <[email protected] > > > >> wrote: > >>> > >>> Inversion means pair(i,j) such that i<j and A[i]>A[j] > >>> > >>> -- > >>> With Regards > >>> Deoki Nandan Vishwakarma > >>> IITR MCA > >>> > >>> > >>> -- > >>> 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. > >> > >> > >> > >> -- > >> Sunny Aggrawal > >> B-Tech IV year,CSI > >> Indian Institute Of Technology,Roorkee > >> > >> -- > >> 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. > > > > > > > > -- > > With Regards > > Deoki Nandan Vishwakarma > > IITR MCA > > > > > > -- > > 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. > > > > > > -- > --Navneet > > -- > 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. > > -- **With Regards Deoki Nandan Vishwakarma IITR MCA * * -- 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. -- 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.
