@@ -131,7 +131,7 @@ The local loss function values then serve as a criterion for choosing the next p
This means that upon adding new data points, only the intervals near the new point needs to have their loss value updated.
The amortized complexity of the point suggestion algorithm is, therefore, $\mathcal{O}(1)$.
The algorithm can be summarized as follows, where `f` is the function to evaluate, and `loss` is the loss function.
The algorithm can be summarized as follows, where `f` is the function to evaluate, `loss` is the loss function, and `heap_push`, `head_pop` and `heap_max` are functions for manipulating a max-heap.
```
data $\gets$ empty_hashmap()
@@ -153,7 +153,7 @@ while heap_max(intervals)[0] > $\epsilon$:
In the above, `loss` only gets the data associated with a single interval;
in order to support loss functions that rely on data from neighboring intervals we would need to maintain a separate datastructure that encodes the neighborhood information.
For example, if `data` were a binary tree storing `(x, f(x))` then we could query neighboring points in $\mathcal{O}(log N)$ time.
For example, if `data` were a binary tree storing `(x, f(x))` then we could query neighboring points in $\mathcal{O}(\log N)$ time.
#### As an example, the interpoint distance is a good loss function in one dimension.
An example of such a loss function for a one-dimensional function is the interpoint distance.