Closest pair in the plane Running time: T(2) = a; T(n) = 2T(n/2) + bn¢log n set c = max(a/2, b) Claim: T(n) · cn¢log 2 n Proof: base case easy… T(n) · 2T(n/2) + bn¢log n · 2cn/2(log n - 1) 2 + bn¢log n < cn(log n)(log n - 1) + bn¢log n · cnlog 2 n April 22, 2014CS38 Lecture 742
{}