**MA Mingyu (Derek)** | 14110562D | Nov 10, 2017

derek.ma | derek.ma@connect.polyu.hk

For A, there are \((n-1)+(n-2)+...+1 = \frac{n^2-n}{2}\) good pairs.

Let \(X\) be a random variable indicate whether a pair of number is a good pair or not. For \(i \in \{1,2,...,\frac{n^2-n}{2}\}\), define an indicator random variable \(X_i = I\{whether\ this\ pair\ is\ a\ good\ pair\}\). \(X_i=1\) indicate it's a good pair between this pair, otherwise \(X_i = 0\).

Then \(X = \sum_{i=1}^{(n^2-n)/2} X_i\).

\(Pr\{pair\ i\ is\ a\ good\ pair\} = 1/2\) because the revert order of this pair exist in another permutation, and these two cases have same probability to happen in one permutation.

By Lemma 5.1, \(E[X_i] = Pr\{pair\ i\ is\ a\ good\ pair\}\).

According to linearity of expectation: \(E[X] = E[\sum_{i=1}^{(n^2-n)/2} X_i] = \sum_{i=1}^{(n^2-n)/2}E[X_i] = \sum_{i=1}^{(n^2-n)/2}1/2 = \frac{n^2-n}{4}\).

```
sort(array P){
sorted_by_digits = sort P according to elements' number of digits \
from smallest to largest using counting-sort \
save as a 2D array
# sorted_by_digits is in form: [[elements with 1 digit],[with 2 digits],...]
# loop the 2D array from smallest one
result = []
for each subarray in sorted_by_digits:
sorted = sort subarray using radix-sort from smallest to largest
result.append(sorted)
return result
}
# call sort(P)
```

The counting-sort for getting `sorted_by_digits`

takes \(O(k)\).

Then for total time complexity of all radix-sorts in the loop:

\[

Total\ Sorting\ Time = \sum{(\#\ of\ digits\ of\ subarray(10+\#\ of\ elements\ in\ subarray))} \\

= \sum{(10\times\#\ of\ digits\ of\ subarray)} + \\

\sum{(\#\ of\ digits\ of\ subarray\times\#\ of\ elements\ in\ subarray

)} \\

= 10k + k \\

= O(k)

\]

So the total time complexity is \(O(k)\).

Transfer this problem into a Exact String Matching Problem, try to match pattern `S`

in string `R+R`

.

```
findShift(String R, String S){
# call fast algorithm for Exact String Matching Problem
result = fastAlgorithm(T = R + R, P = S) # S is the pattern
if there are some output for matching position in result
return 'YES'
else
return 'NO'
}
# call findShift(R, S)
```

The time complexity is mainly the time for the fast algorithm which is \(\Theta(2|R|+|S|)\). So the time complexity is \(O(|R|+|S|)\).

If \(P = <(2,0), (5,1), (4,1.1), (2,4)>\), for point \((4,1.1)\), it's a maximal with respect to \(P\), but it's not on the convex hull. The following figure can illustrate the situation clearly:

```
findMaximal(array of points P){
sorted_by_x = sort P according to points' x value from largest to smallest \
using merge-sort, save as 2D array
# sorted_by_x is in form: [...,[point(s)],[point(s)],[point(s) at largest x]]
maximalList = []
yMaxGlobal = 0
for each array in sorted_by_x:
# get the point with largest y value at this x
yMax = 0
for each element in array:
if (element.y >= yMax):
yMax = element.y
maxYPoint = element
# compare with global max y value
if (maxYPoint.y > yMaxGlobal):
# if the point with largest y at this x is larger than previous max y value
# then this point is maximal
maximalList.append(maxYPoint)
yMaxGlobal = maxYPoint.y
return maximalList
}
# call findMaximal(P)
```

In this algorihtm, the time complexity of sorting by x value is \(O(nlgn)\). The loop in the loop to get the point with largest y value in that x will scan every individual points in P, so the time complexity is \(O(n)\). All in all, the dominant time complexity is the sorting, thus the total time complexity is \(O(nlgn)\).