Function approximation from list of numbers in linear time so what I need is a bit hard to describe for me, so I start with giving a context:
I have a list of numbers that is not sorted (yet).
One part of a more complex algorithm is that I need a rough approximation of a list of arbitrary numbers so that I can throw a number into that approximation and it returns a likely position in the list (after I sorted the list).
What I am doing right now is to get the smallest and biggest number in the list and just create a straight line through them and use this as my approximation. This way I can "sort in" all the other numbers on the line. As I already mentioned, a rough approximation is sufficient, that is why I need it in linear time (a full sort would require O(n). My approach with the straight line already delivers acceptable results, but the better my approximation the faster the whole algorithm will run, so my question is: Can I somehow get a more accurate approximation in linear time?
 A: What you're doing is selecting the elements at indices (in the sorted list) $0$ and $n$ and performing a linear fit between them in order to approximate your list. A generalization of this is to select the elements at indices $0, \lfloor n/k\rfloor, \lfloor 2n/k\rfloor,\ldots,n$ for some $k\geq 1$, and then perform a piecewise linear fit between them. For any fixed $k$ there is a randomized algorithm for this which runs in expected linear time, although the constant factor will grow with $k$. There's probably a deterministic linear time algorithm as well, but I only know of one for $k=1,2$ and even when $k=2$ the algorithm is complicated and has a large constant factor. The algorithm just comes from a simple algorithm for finding the element of index $i$ in a list $A$ (after sorting) for any $i$.
$\mathrm{FIND}(A,i)$:


*

*Choose a random $x\in A$.

*Partition $A\setminus \{x\}$ into $A_1$ and $A_2$ such that $A_1=\{y\in A:y<x\}$ and $A_2=\{y\in A:y>x\}$.

*If $|A_1|=i$ return $x$.

*If $|A_1|<i$ return $\mathrm{FIND}(A_2, i - |A_1|-1)$.

*If $|A_1|>i$ return $\mathrm{FIND}(A_1, i)$.


In order to find the elements of indices $0, \lfloor n/k\rfloor, \lfloor 2n/k\rfloor,\ldots,n$ all you have to do is run $\mathrm{FIND}$ $k+1$ times. Drawing a straight line from the $0$th element to the $\lfloor n/k\rfloor$st, the $\lfloor n/k\rfloor$st to $\lfloor 2n/k\rfloor$st, etc. gives you the desired approximation.
