Given a sorted array A[1...n] of arbitrary real numbers For each i ∈ [1 ... n-1]; A[i+1] - A[i] is the i-th gap of A.
a) Compute the average gap of the n-1 gaps of A. --Try 1: In O(n) time, iterate over A and add each gap to a 'GapSum'. GapSum/n-1 = average gap
b) By the law of averages, there must be some i ∈ [1 ... n-1] such that the i-th gap of A does not exceed the average gap of A. Any such i-th gap is called a short gap. Find a short gap of A. --Try 1: Obvious O(n) -- check each gap, return smallest. Is there an asymptotically faster divide and conquer algoriithm to find a short gap of A?
I'm kind of stuck as to how I could do this any faster? Is there a property of averages that I am perhaps overlooking. Any direction would be helpful.
--edit-- Nico commented that the average gap could be calculated in constant time. Would this count as constant time: The only idea I have to be able to calculate the average gap in constant time is to prepare an auxillary array before computation where it stores the sum of the gaps upto i in B[i]. Then calculating the average gap would be B[n-1]/n-1
Given that A is sorted, have constant-time lookup and you know n, you can calculate the average gap size in constant time by taking the difference between the first and last element and dividing by n.
a. Iterate through A and return the first gap less than or equal the average. No need to find the smallest gap. Your run time will still be in O(n), though.
b. Can you do better? Consider doing something similar to a binary search: Calculate the average gap size of the two halves of the array. The one with a lower average have to contain at least one short gap, so you can search within only that half. Recursively do the same thing in that half and you may end up with a O(log n) algorithm!