Suppose that I have $$\lim_{k,l,m \rightarrow \infty}(f(x,l) ~~=~~ \sum_{n=1}^{m} g(a_{n,k})h(x,n)$$ where the $a_{n,k}$ are pseudo-random real numbers with $k$ digits generated in an arbitrary way, and $g,h$ are functions. At the limit, let the sum be equal to the function. Let's be interested in the approximations at $k$ digits and $l$-digit precision in the function $f$.What would be an estimate of the time-complexity $O(u(m),v(k),z(l),f)$ to fit the function $f(x)$ by trial and error to a demanded precision $l$, as a function of the chosen number of finite terms $m$ in the sum, the $k$ digits of the random numbers $a_{n,k}$? For simplicity, assume that $f$ has a taylor series, and for concreteness, let $f$ be the sine function.
Time complexity of polynomial regression with random coefficients
time complexity;randomized algorithms;polynomial time;pseudorandomness