A DO lies between these two extremes. It uses less than O(n^2) space in order to answer queries in less than O(m + n \log n) time. Most DOs have to compromise on accuracy, i.e. they don't return the accurate distance but rather a constant-factor approximation of it.
