Consider algorithms based on the divide & conquer paradigm

SmallestDist(A[1..n])

if n = 1

return

else if n = 2

return D(A[1], A[2])

else m n/2

d1 SmallestDist(A[1..m])

d2 SmallestDist(A[m + 1..n])

d0 min(d1, d2)

return CrossDist(A[1..n], m, d0)

where CrossDist(A[1..n], m, d0) returns the minimum of d0, and the smallest distance between a point inA[1..m] and a point in A[m + 1..n].

First assume that CrossDist is implemented in the naive way:

CrossDist(A[1..n], m, d0)

d d0

for i 1 to m

for j m + 1 to n

d min(d, D(A[i], A[j]))

return d

With this implementation, analyze SmallestDist to give precise and simple bounds for the asymptotic behavior of D(n) and T(n). D(n) which the number of calls to the function D and T(n) which is the overall running time.