考虑分治版本的二维最近对算法，在每次递归调用时，都简单地对两个集合C1和C2分别哪找它们Y轴坐标的升序进行排列。假设使用的是合并排序，请建立最差运行时间的近似递推关系，并在n=2^k 的条件下进行求解。

假设在每次递归调用中，需要花费O(nlogn)的时间将两个集合按Y轴坐标进行排序，然后需要花费线性的时间将集合中距离分界线小于d的点对找出来。设T(n)表示分治版本的二维最近对算法在n个点下的最差运行时间，则有：

T(n) = 2T(n/2) + O(nlogn) + O(n)

其中2T(n/2)表示将n个点分为两部分求解最近对问题所需的时间，O(nlogn)表示对这两部分进行排序所需的时间，O(n)表示在合并这两个集合时需要线性时间内找到距离分界线小于d的点对。

我们假设n=2^k，将递推式展开，有：

T(2^k) = 2T(2^{k-1}) + O(2^k log(2^k)) + O(2^k)
= 2[2T(2^{k-2}) + O(2^{k-1}log(2^{k-1})) + O(2^{k-1})] + O(2^k log(2^k)) + O(2^k)
= 4T(2^{k-2}) + O(2^k log(2^{k-1})) + 3O(2^{k-1}) + O(2^k)
= 8T(2^{k-3}) + O(2^k log(2^{k-2})) + 7O(2^{k-2}) + 3O(2^{k-1}) + O(2^k)
= 2^k T(1) + kO(2^k log2) + Σ_{i=0}^{k-1}(2^i - 1)O(2^{k-i})
= O(n) + O(nlogn) + Σ_{i=1}^{k-1}2^iO(2^{k-i}) （令T(1)=O(1)）
= O(nlogn) + Σ_{i=1}^{k-1}O(2^k)
= O(nlogn) + O(n2^{k-1})
= O(nlogn)

因此，分治版本的二维最近对算法在n=2^k的情况下的最差运行时间为O(nlogn)。