1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
Nastasia [14]
3 years ago
8

Recall the problem of finding the number of inversions. As in the text, we are given a sequence of n numbers a1, . . . , an, whi

ch we assume are all distinct, and we define an inversion to be a pair i < j such that ai > aj.
We motivated the problem of counting inversions as a good measure of how different two orderings are. However, one might feel that this measure is too sensitive. Let’s call a pair a significant inversion if i < j and ai > 2aj. Give an O(n log n) algorithm to count the number of significant inversions between two orderings.
Computers and Technology
1 answer:
Kay [80]3 years ago
5 0

Answer:

The algorithm is very similar to the algorithm of counting inversions. The only change is that here we separate the counting of significant inversions from the merge-sort process.

Algorithm:

Let A = (a1, a2, . . . , an).

Function CountSigInv(A[1...n])

if n = 1 return 0; //base case

Let L := A[1...floor(n/2)]; // Get the first half of A

Let R := A[floor(n/2)+1...n]; // Get the second half of A

//Recurse on L. Return B, the sorted L,

//and x, the number of significant inversions in $L$

Let B, x := CountSigInv(L);

Let C, y := CountSigInv(R); //Do the counting of significant split inversions

Let i := 1;

Let j := 1;

Let z := 0;

// to count the number of significant split inversions while(i <= length(B) and j <= length(C)) if(B[i] > 2*C[j]) z += length(B)-i+1; j += 1; else i += 1;

//the normal merge-sort process i := 1; j := 1;

//the sorted A to be output Let D[1...n] be an array of length n, and every entry is initialized with 0; for k = 1 to n if B[i] < C[j] D[k] = B[i]; i += 1; else D[k] = C[j]; j += 1; return D, (x + y + z);

Runtime Analysis: At each level, both the counting of significant split inversions and the normal merge-sort process take O(n) time, because we take a linear scan in both cases. Also, at each level, we break the problem into two subproblems and the size of each subproblem is n/2. Hence, the recurrence relation is T(n) = 2T(n/2) + O(n). So in total, the time complexity is O(n log n).

Explanation:

You might be interested in
List five things that could cause premature bearing failure
Wewaii [24]
Smoking, Drinking, Use of drugs, problems with uterus, Problems with cervix or placenta.


6 0
3 years ago
How does design influence the product's function?
r-ruslan [8.4K]
I think the answer is
8 0
3 years ago
Buying a new computer for which of these reasons is most likely a sound
Svetllana [295]

Answer:

b. you need it to do your homework

Explanation:

3 0
2 years ago
Which site acquired by Warner Bros. in 2011 allows users to rate movies and watch movie trailers?
mel-nik [20]
It was flixter.
hope this helps
7 0
3 years ago
Read 2 more answers
Which of the following is a neurotransmitter? Select one:
jenyasd209 [6]
B. Dopamine would be the right answer!! 
7 0
3 years ago
Other questions:
  • To protect the computer network of a large organization, network engineers monitor network traffic. This traffic is compared to
    13·2 answers
  • With network management software, a network manager can ____.
    6·1 answer
  • Documents on the web stored on web servers are known as web _____.
    6·1 answer
  • The PICC team is scheduled to remove a PICC before client discharge. Assessment of the catheter indicates the PICC and determine
    7·1 answer
  • In this question, you must create a function in C++ using an external editor. When satisfied with your work, you shall attach it
    10·1 answer
  • Implementations <br> in c++ programming when finding lcm and gcd in c++​
    12·1 answer
  • Case Study/Scenario: First, Julio clicks Tools from the Chrome menu on the toolbar. Next, he looks for Manage Add-Ons but can no
    9·1 answer
  • 50 points! ㅠㅠ does anyone speak korean or watch korean animes? 안녕 ㅋㅋ ㅇㅅㅇ How do people make animationsss.
    8·2 answers
  • Hilarious error messages
    10·2 answers
  • What is your favorite song? mine is "In the final"
    7·2 answers
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!