I have a function $f(n)$ which is hard to evaluate, but which can be well-approximated as $an+b$ for unknown real constants $a,b.$ Say the time needed to evaluate $f(n)$ is $b(n)$ where $b$ is sufficiently nice. (In the example immediately at hand, $b(n)=n^2,$ and the errors $|an+b-f(n)|$ seem quite small, logarithmic or possibly even bounded; make reasonable assumptions as needed.)
I would like to spend a certain amount of time to estimate $a$ (or $a,b$) as precisely as possible. I could compute $a(1),a(2),\ldots,a(n)$ for some $n$ (in my example, costing about $n^3/3$), but the interior points won't end up mattering much. At the other extreme, I could evaluate $f(1)$ and $f(m)$ with $m$ as large as I can afford (in my example, $kn^{1.5}$ with $k\approx0.58$) and fit a line; this gives maximal separation but is subject to errors. A similar approach would be to evaluate a few points near 1 and a few points as high as possible.
I understand that this question is under-specified: I don't know the distribution of the error term, I haven't specified which metric (I was using $L^2$ in my example, but it doesn't need to be that), etc. I'm hoping that there is a good method which will suggest natural parameters. Often good answers require tweaking the question a bit. :)