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
The Windows Operating System: A) is a web-based operating system for the Internet era. B) is a data management application used
NNADVOKAT [17]

The Windows Operating System is an operating system used on most Wintel PCs throughout the world.

E) is an operating system used on most Wintel PCs throughout the world.

<u>Explanation:</u>

An operating system can be defined as a system software whose main function is to act as an interface between the user and the computer.  It performs different administrative elements of a PC and gives a graphical UI to the client with the goal that they can impart to the PC.  

Wintel is a PC exchange industry term for PCs dependent on the Intel chip and one of the Windows working frameworks from Microsoft. In the zone of work area and smart phones, Windows is commonly above 70% in many markets and at 78% all inclusive, Apple's macOS at around 14%, Google's ChromeOS at about 3% (in North America) and Linux at around 2%.  

The term Wintel PCs originate from the mix of two words: Windows and Intel, which allude to the PCs that work on the Windows Operating System and use Intel Processors.

6 0
3 years ago
In the Budget Details sheet, if you wish to autofill with the formula, you must use a ______ reference for the LY Spend Total ce
ahrayia [7]

Answer:

The answer is A.Absolute reference.

Explanation:

Absolute reference is a cell reference whose location remains constant when the formula is copied.

8 0
3 years ago
Which device performs the function of determining the path that messages should take through internetworks?.
bija089 [108]

Answer:

A router

Explanation:

8 0
2 years ago
Write code that inserts useritems into the output string stream itemsoss until the user enters "exit". each item should be follo
Yuliya22 [10]
If user output is ''red purble yellow exit'': red purple yellow  import java.util.Scanner;  import java. io.PrintWriter;  import java. io.StringWriter;    public class StringStreamOutput {   public static void main (String [] args) {   Scanner snr = new Scanner(Scanner.in);   Stringuseritem = '''';    StringWriter itemcharStream = new StringWriter();  PrinterWriter itemsOSS = new PrintWriter(itemcharStream);    System.out.printIn(''Enter items (type Exit to open):'');  useritem = scnr.next();    while (!userItems.Equals(''Exit'')) {  /*Your solution goes here*/     UserItem = scnr.nxt();    }     useritem = itemCharStream.toString()   System.out.printin(useritem);     return;     }    }
5 0
3 years ago
Smartphones combine the features of which two types of devices?
tankabanditka [31]
Idunno if you got the answer to this question or if I'm too late, feel free to message me if I'm not!
6 0
2 years ago
Read 2 more answers
Other questions:
  • When you enter search keywords in the search box of file explorer and the onedrive option is selected?
    15·2 answers
  • Methods for preventing/overcoming group conflict include all EXCEPT:
    10·1 answer
  • Daniela’s company has made the decision to allow employees to work from home as the company has outgrown their physical space. K
    13·1 answer
  • A marketing associate wants to use the Validate button to ensure an email is CAN-SPAM compliant. What information does the assoc
    5·2 answers
  • what tool can a student use to make sure his or her work paper does not take credit for someone else's work ?
    5·1 answer
  • A system that provides monthly production figures for a manager at manufacturing facility is considered a(n) __________. a. ente
    7·1 answer
  • Show the stack with all activation record instances, including static and dynamic chains, when execution reaches position 1 in t
    6·1 answer
  • Which of the following is true of functions?
    10·1 answer
  • Robyn needs to ensure that a command she frequently uses is added to the Quick Access toolbar. This command is not found in the
    11·1 answer
  • Vector images take up much less space when saved to a computer or storage device because computers and storage devices just need
    14·2 answers
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!