Purchase Solution

order-statistic tree to count the number of inversions

Not what you're looking for?

Ask Custom Question

Need help to show 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?

Purchase this Solution
Solution Summary

Advice on 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) is offered.

Solution Preview

Please see the attached file.

We use an order statistic tree according to the attribute key[.]. Store with each node the original index in the sequence, an integer between 1 and n which we shall call index[.]. Let size[x] be the size of the subtree rooted at node x. Let left[.] and ...

Purchase this Solution
Free BrainMass Quizzes
C++ Operators

This quiz tests a student's knowledge about C++ operators.

Javscript Basics

Quiz on basics of javascript programming language.

Inserting and deleting in a linked list

This quiz tests your understanding of how to insert and delete elements in a linked list. Understanding of the use of linked lists, and the related performance aspects, is an important fundamental skill of computer science data structures.

Excel Introductory Quiz

This quiz tests your knowledge of basics of MS-Excel.

Basic Computer Terms

We use many basic terms like bit, pixel in our usual conversations about computers. Are we aware of what these mean? This little quiz is an attempt towards discovering that.

View More Free Quizzes
Related BrainMass Solutions

  • binary search tree

    In this project, you need to define a print function that prints tree elements in in-order as well as a count function that counts and returns the number of tree nodes in a binary search tree. In addition you need to complete the main function.

  • Inversions of permutation

    13913 Inversions of Permutation Found Find the number of inversions in the following permutation: (3, 2, 1) The number of inversions in the permutation: (3, 2, 1) I = n(n-1)/2 =3*(3-1)/2=3 This shows how to find the number of inversions in a

  • c++ trees

    Constitution), that is, count how many times each different value appears in the list and then print out each value along with its count (frequency). The output should be arranged from smallest to largest value (in alphabetical order).

  • C++ Binary Tree Sorting of text words

    The same word will not be inserted twice in the tree. 4) Print the number of comparisons done and the CPU time used in part 3.

  • Significant Inversions Algorithm : Inversion Pairs

    Give an O(n*log(n)) algorithm to count the number of significant inversions in the input sequence. Use quick sort to sort the sequence S as sorted sequence S' as A1', A2', ...., An', time is n*log(n).

  • C++ ordered binary tree: inorder, preorder, postorder

    Print out the tree in postorder. d. Print out the number of nodes in the tree. (Traverse the tree and count the nodes.) e. Sum up all the values in the tree and compute the average. f. Count the number of leaves in the tree. g.

  • Constructing a tree diagram for different bicycle combination

    The solution includes a count of possible bicycle combinations and a tree diagram.

  • Chromosomal inversions or deletion with human disorders

    Inversions have played an important role in the evolution of sex chromosomes. In groups like mammals, the Y chromosome is unable to undergo recombination with the X chromosome along almost its entire length.

  • C++ Binary Search Tree

    Write a recursive member function leafCount() for class template BST to count the leaves in a binary tree. [Hint: How is the number of leaves in the entire tree related to the number of leaves in the left and right subtrees of that root?]

View More Related Solutions