O(m+n) Algorithm for Linear Interpolation


Problem

Given data consisting of $ n$ coordinates $ \left((x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)\right)$ sorted by their $ x$ -values, and $ m$ sorted query points $ (q_1, q_2, \ldots, q_m)$ , find the linearly interpolated values of the query points according to the data. We assume $ q_i \in (\min_j x_j, \max_j x_j)$

I heard off-hand that this problem could be solved in $ O(m+n)$ time but can only think of an $ O(m \log n)$ algorithm. I can’t seem to find this particular problem in any of the algorithm textbooks.

Linearithmic Algorithm

interpolated = [] for q in qs:     find x[i] such that x[i] <= q <= x[i+1] with binary search     t = (q - x[i]) / (x[i+1] - x[i])     interpolated.append(y[i] * (1-t) + y[i+1] * t) 

This gives us a runtime of $ O(m \log n)$ , it’s unclear to me how to get this down to $ O(m + n)$ as the search for $ x_i$ must be done for every query point.