FREE Trial

Let A[1 n] be an array of n distinct numbers. If i < j and A[i] > A[j], then

Question:

Let A[1 ¬ n] be an array of n distinct numbers. If i < j and A[i] > A[j], then the pair (i, j) is called an inversion of A.
a. List the five inversions of the array ¬2, 3, 8, 6, 1¬.
b. What array with elements from the set {1, 2, . . . , n} has the most inversions? How many does it have?
c. What is the relationship between the running time of insertion sort and the number of inversions in the input array? Justify your answer.
d. Give an algorithm that determines the number of inversions in any permutation on n elements in Θ (n lg n) worst-case time. (Hint: Modify merge sort.)

This problem has been solved!


Do you need an answer to a question different from the above? Ask your question!

Step by Step Answer:

Answer rating: 64% (14 reviews)

a The inversions are 1 5 2 5 3 4 3 5 4 5 Remember that inversions are specified by indices rather than by the values in the array b The array with ele…View the full answer


answer-question
Answered By
tutor-profile-image
PALASH JHANWAR
I am a Chartered Accountant with AIR 45 in CA - IPCC. I am a Merit Holder ( B.Com ). The following is my educational details. PLEASE ACCESS MY RESUME FROM THE FOLLOWING LINK: https://drive.google.com/file/d/1hYR1uch-ff6MRC_cDB07K6VqY9kQ3SFL/view?usp=sharing
3.80+ 3+ Reviews 10+ Question Solved
Related Book For  answer-question
Data Structures and Algorithms in Java

Data Structures and Algorithms in Java

ISBN: 978-1118771334

6th edition

Authors: Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser

See More Books
View Solution
Create a free account to access the answer
Cannot find your solution?
Post a FREE question now and get an answer within minutes. * Average response time.
Question Posted: July 13, 2010 02:39:14
See More Questions

Students also viewed these Computer Sciences questions

Q:
Let A[1 .. n] be an array of n distinct numbers. If i < j and A[i] > A[j], then the pair (i, j) is called an inversion of A. (See Problem 2-4 for more on inversions.) Suppose that each element of A...
A:
Let X be an indicator random variable for the event where the pair A i A......
Q:
Give an algorithm that determines whether or not a given undirected graph G = (V, E) contains a cycle. Your algorithm should run in O (V) time, independent of |E|.
A:
An undirected graph is acyclic i e a forest if and only if a DFS yields no back edges......
Q:
Let B be an array of size n 6 containing integers from 1 to n5 inclusive, five of which are repeated. Describe an algorithm for finding the five integers in B that are repeated.
A:
Sort the array B then scan it......
Q:
Split the number 750 into two numbers x and y so that the sum of 8% of the first number and 24% of the second number is 11.2% of the sum of x and y.
A:
Given number a 750 According to question 8 W 24 1......
Q:
Would it be appropriate to say that a distribution with a standard deviation of 10 centimeters is more dispersed than a distribution with a standard deviation of 5 inches? Support your position.
A:
No It is not appropriate to compare standard......
Q:
The data set SMOKE.RAW contains information on smoking behavior and other variables for a random sample of single adults from the United States. The variable cigs is the (average) number of...
A:
The variable cigs has nothing close to a normal distribution in the p......
Q:
How should we operate a mixed flow reactor so as to maximize the production of R? Separation and recycle of unused reactant is not practical. Under ultraviolet radiation, reactant A of C A0 = 10...
A:
Click to View...
Q:
Presented below are account balances for Monterey Hospital. In addition, cash transactions for the year ended December 31, 2012, are summarized in the T-account. Required: Using the information above...
A:
Monterey Hospital Statement of Operations For the year ended 12 31 2012 Unrestricted Operating Revenues Net Patient Service Revenue 9 480 000 Net Assets Released from Time Restrictions 19 600 Total Op......
Q:
1. Create a program that will go through a NULL-terminated string of ASCII characters and convert any uppercase letters to lowercase letters. (The ASCII NULL character is Ox00.) Any changes should...
A:
Below is a simple assembly program that converts uppercase letters to lowercase in a NULL terminated......
Q:
A ride hailing company has their DB structured in 3 major tables as described in the SCHEMA section below. Write a query to fetch the top 100 users who traveled the most distance using the service....
A:
SELECT TOP 100 USERS name SUM RIDES distance AS distance traveled FROM USERS INNER JOIN RIDES ON RID......
Q:
The next two parts will prove inequality (2.3). b. State precisely a loop invariant for the for loop in lines 2-4, and prove that this loop invariant holds. Your proof should use the structure of the...
A:
a We need to show that the elements of A form a permutation of the elements of A b Loop invariant At the start of each iteration of the for loop of lines 24 A j min A k j k n and the subarray A j n is......
Q:
a. Rank the following functions by order of growth; that is, find an arrangement g1, g2, ..., g30 of the functions satisfying g1 = Ω(g2), g2 = Ω(g3), ..., g29 = Ω(g30). Partition...
A:
a Here is the ordering where functions on the same line are in th......
Q:
Why does the post-closing trial balance contain only balance sheet accounts?
A:
All the income statement or temporary accounts and the W......
Q:
Perry decides to wait until his niece starts kindergarten to start her college fund. If he is depositing $100 per month into an account that pays 10%, how much will there be for her in 13 years?...
A:
SOLUTION a To calculate the amount that will be in Perry s niece s college fund in 13 years we can u......
Q:
Which of the following is NOT a key element of the definition of ethics? A. Reflective choice B. Moral principles C. Definitive conclusions D. Consequences of decisions
A:
The detailed answer for the above question is provided below C Definitive conclusions Definitive conclusions are not a key element of the definition o......
Q:
What is the place holder "X"? Why is it used? Provide 2 examples of ICD-10-CM with "X" as place holders. Each code should be have a full definition.
A:
In the context of ICD 10 CM International Classification of Diseases 10th Revision Clinical Modifica......
Q:
What is the role of Consumer and Business Services in relation to real estate legislation in South Australia?
A:
Consumer and Business Services CBS plays a significant role in relation to real estate legislation in South Australia CBS is a government agency responsible for regulating various industries including......
Q:
McCabe Corporation issued $560,000 of 7% 10-year bonds. The bonds are dated and sold on January 1, 20X1. Interest payment dates are January 1 and July 1. The bonds are issued for $521,724 to yield...
A:
To calculate the interest expense for the first semiannual interest payment on July 1 20X1 usin......
Q:
A, B and C are partners sharing profits and losses in the proportion of 3 : 2 : 1 and their Balance Sheet on 31st December, 2017 stood as under : B died on 28th February 2018 and according to the...
A:
To account for the death of partner B and the settlement with his executors we need to pass the necessary journal entries and prepare the accounts Let......
Q:
What is taxable income, and what is the formula for determining taxable income?
A:
Taxable income is the amount of income su......
Algorithmic Trading With Interactive Brokers Python And C++ 1st Edition - ISBN: 0997303735 - Free Book