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
joe is in the planning stages to make sure that an upcoming company promotion during a major sporting event will not overwhelm h
VikaD [51]

The possible solutions to recommend are that Vertical scaling, Horizontal scaling, Cloud bursting

The cloud computing business model is based on a utilitarian business model, which charges you solely for the resources you use. With this strategy, you may scale your cloud fleet to suit its present workload and add and subtract capacity as needed. Variability may be used to scale cloud services in a variety of ways, including vertical and horizontal scaling and bursting. Horizontal scaling in cloud computing refers to adding more instances rather than switching to a bigger instance size. Vertical scaling involves the addition of more or faster CPUs, memory, or I/O resources to an existing server or the replacement of one server by a more physical server.

Learn more about the utility business model here: brainly.com/question/28668154brainly.com/question/29349562

#SPJ4

3 0
1 year ago
What is a Windows feature that allows you to temporarily store text?
nata0808 [166]
This would be copy and paste.

When you select a text, you can use your keys CTRL and C to copy that same selected text. After this, you can use the paste feature by selecting CTRL and V. Doing this, your selected text will be copied and pasted to a certain location. 
3 0
3 years ago
Which of the following are characteristics of a good webmail message select all that apply
emmainna [20.7K]

add choices please :)


6 0
3 years ago
Doe's anyone know how to access developer mode on a Chromebook laptop if enterprise enrollment blocks it?
Mekhanik [1.2K]
♥ <span>Boot your Chromebook into recovery Mode
(Escape refresh and power keys all need to be help down)
It </span><span>will then  reboot into recovery mode
♥ </span><span>Press Ctrl+D at the recovery screen
♥ </span><span>To turn the Verification off you will need to press the enter button.
♥ and then you have it :D 

</span>
8 0
3 years ago
Read 2 more answers
Which of the following statements are true?
grin007 [14]

Answer:

I think the answer are two which are B and C

7 0
3 years ago
Other questions:
  • Which data type stores images and audio visual clips?
    9·2 answers
  • A hard drive that is running slowly may not have been
    10·2 answers
  • This program will get you used to retrieving a value from a function. The function should be named getRandomNumber. The function
    15·1 answer
  • What will the following program display?
    15·1 answer
  • The Fibonacci numbers are the numbers
    15·1 answer
  • Which of the following could not be represented by columns in the SPSS data editor? a. Levels of between-group variables. b. Lev
    11·2 answers
  • What is anatomy of software house?
    10·1 answer
  • To remove text from a specific location and keep it to use again, you should select ___
    6·1 answer
  • My game is telling me to "Press any key." Where is the "any" key?????
    13·1 answer
  • Many of the first photographers were actually scientists and inventors. True or false?
    7·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!