This an algorithm to count `inversions`

in an `array`

, this is a `divide and conquer`

algorithm, I want to know what is the `basic operation`

of the this algorithm and how do I set up a `recurrence relation`

to analyze `number of execution`

of the basic step?

The `definition`

of `basic step`

: The operation contributing the most to the total running time of an algorithm.

– It is typically the most time consuming operation in the algorithm’s innermost loop.

• Examples: Key comparison operation; arithmetic operation (division being

the most time-consuming, followed by multiplication)

this is the algorithm

```
public static int merge(int() arr, int() aux, int low, int mid, int high)
{
int k = low, i = low, j = mid + 1;
int inversionCount = 0;
// while there are elements in the left and right runs
while (i <= mid && j <= high)
{
if (arr(i) <= arr(j)) {
aux(k++) = arr(i++);
}
else {
aux(k++) = arr(j++);
inversionCount += (mid - i + 1); // NOTE
}
}
// copy remaining elements
while (i <= mid) {
aux(k++) = arr(i++);
}
// no need to copy the second half
// copy back to the original array to reflect sorted order
for (i = low; i <= high; i++) {
arr(i) = aux(i);
}
return inversionCount;
}
// Sort array `arr(low…high)` using auxiliary array `aux`
public static int mergeSort(int() arr, int() aux, int low, int high)
{
// Base case
if (high == low) { // if run size == 1
return 0;
}
// find midpoint
int mid = (low + ((high - low) >> 1));
int inversionCount = 0;
// recursively split runs into two halves until run size == 1,
// then merges them and return up the call chain
// split/merge left half
inversionCount += mergeSort(arr, aux, low, mid);
// split/merge right half
inversionCount += mergeSort(arr, aux, mid + 1, high);
// merge the two half runs
inversionCount += merge(arr, aux, low, mid, high);
return inversionCount;
}
```

**how do I set up a recurrence relation to analyze number of execution of the basic operation? Please also provide explanation!!**