Order statistic tree to count number of inversions in array

Assignment Help Data Structure & Algorithms

Reference no: EM1380205

Demonstrate how to use an order-statistic tree to count the number of inversions in an array of size n in time O(n lg n).

Note that we call a pair (i,j) an inversion if i < j, but key[i] > key[j]. Thus, an increasing sequence has no inversions. A decreasing list has the maximum number of inversions, n(n-1)/2.

I believe we start by letting k be the number of inversions in the sequence. We then create an order-statistic tree and store with each node the original index in the sequence.

Is there anything else we store in the node and what would be the algorithm for the number of inversions?

Reference no: EM1380205

Questions Cloud

Income tax project : osalyn uses the Cash Method Of Accounting for Federal Income Tax purposes for her business, ROSALYN'S BOOKSTORE, and the business code for the business for Federal Income Tax purposes

Definition of a method isreverse : Provide the definition of a method, isReverse , whose two parameters are arrays of integers of equal size. The technique returns true if and only if one array is reverse of the other.

Finding majority element : Let A be an array of n elements. An element x is said to be a majority element in A if it occurs in A more than n/2 times.

Creating application - two dimensional array : Make an application that either sums or averages rows or columns of a 2-dimensional array depending on user choices.

Order statistic tree to count number of inversions in array : Demonstrate how to use an order-statistic tree to count the number of inversions in an array of size n in time O(n lg n).

Creating java program using two arrays : Create a program in Java which defines 2-unconstrained arrays of user defined length n, that contain n Random numbers each and which outputs addition of pairs of elements.

Calculations on rows and columns of an array : Make a menu bar with a document menu that includes a Perform Action command and an Exit command. The Perform Action command calculates either the sum or the average of rows or columns in array and displays result in a message box.

Programming language problems : Many programming languages do not permit you to ask two or more questions in a single comparison by using a logical And Operator

Data systems and design : Suppose if you have a program with a housekeep() module, a mainloop() module, and a finishup() module, when is the second input record usually read?

User Account

All Pages