Problem
Let S = (s1, ..., sn) be a list of n distinct natural numbers. Describe in words how would be an algorithm to check in subquadratic time if there is a pair of numbers si and sj such that |si - sj| ≤ log n. That is, the time complexity function T(n) must satisfy limn→∞ T(n)/n2 = 0. Assume that log n can be evaluated in O(1).