content_image/306310.jpg
where T$_{i}$ ( w ) = ∑ C ∈C ( w ) , r$_{l}$ ̸ =1 ∩ r$_{h}$ ̸ = N t$_{C}$ and T$_{e}$ ( w ) = ∑ C ∈C ( w ) , r$_{l}$ =1 ∪ r$_{h}$ = N t$_{C}$ . The algorithm proceeds as follows. First, in a preprocessing phase, we calculate T$_{i}$ ( w ) and T$_{e}$ ( w ) for all w ∈ { 1 , . . . , N } . Since t$_{C}$ can be calculated in O (1), as described above, the calculation of T$_{i}$ ( w ) and T$_{e}$ ( w ) for a fixed w takes O ( N ). Since there are N values for w , we can compute and store all values of T$_{i}$ ( w ) and T$_{e}$ ( w ) in O ( N $^{2}$). Also in the preprocessing phase, for all u, v ∈ { 0 , . . . , N } we calculate and store all ( u v $^{)}$. This can be done in O ( N $^{2}$) using Pascal’s triangle method. 

Given T$_{i}$ ( w ) , T$_{e}$ ( w ) , w = 1 , . . . , N − 1 (which are independent of m!), and all ( u v $^{)}$, we can clearly calculate S$_{m}$ according to equation (3.2) for any m in O ( N ) and therefore for all m s in O ( N $^{2}$), since m < N . Therefore the overall complexity of computing the scores for all m s is O ( N $^{2}$). 

## 3.1.2 Algorithm for the independence problem 

Let r$_{i}$ be the rank of x$_{i}$ among the observed x values, and s$_{i}$ is the rank of y$_{i}$ among the y values The algorithm first computes the empirical cumulative distribution in O ( N $^{2}$) time and space, 

<img src='content_image/306310.jpg'>

where A (0 , s ) = 0 , A ( r, 0) = 0 and ˆ F ( r, s ) = A ( r, s ) /N . First, let B be the ( N + 1) × ( N + 1) zero matrix, and initialize to one B ( r$_{i}$, s$_{i}$ ) for each observation i = 1 , . . . , N . Next, go over the grid in s -major order, i.e., for every s go over all values of r , and compute: 

1. A ( r, s ) = B ( r, s − 1) + B ( r − 1 , s ) − B ( r − 1 , s − 1) + B ( r, s ), and 

2. B ( r, s ) = A ( r, s ). 

