0

I'm trying to approximate unknown function, given x and f(x) values. The function itself represents computational complexity of an algortihm, so it can be polynomial, logarithmic, exponential etc. I'm not sure whether such approximation method exists and if it's doable. I mostly find information about polynomial approximation everywhere, but that's not what I'm looking for I guess. I would be really grateful for any tips about method or algorithm that you think may be suitable. Or any approach to the problem actually.

softkdp
  • 3
  • 2
  • The computational complexity of an algorithm can be anything, so that will not help (much). Exponential is not the upperbound. For example, the [*exponential hierarchy*](https://en.wikipedia.org/wiki/Exponential_hierarchy) contains complexity classes that scale larger than exponential. – Willem Van Onsem Jul 17 '19 at 18:53
  • Since (as per comment above) the function you want to approximate can be anything, polynomial approximation is as good as any. The reason you see it 'everywhere' is because it is well suited to numerical computation. How well you will need your function approximated entirely depends on what you want to do with the approximation. – peter.cntr Jul 17 '19 at 19:50
  • polynomial interpolation/approximation is not usable on too fast growing functions. So what you need to do is determine growth class and use approximation related to it ... As complexities tend to be monotonic You can fit the coefficients with binary search. See [Finding the mathematical algorithm to which matches an input and output together](https://stackoverflow.com/a/31510038/2521214) I think the top limit of growth classes are described by [Ackermann function](https://en.wikipedia.org/wiki/Ackermann_function) – Spektre Jul 18 '19 at 08:06
  • In case of big growths I think this might help a bit: [How to express tetration function, for complex numbers](https://stackoverflow.com/a/56735614/2521214) which is Ackermann related. For polynomials see [How can i produce multi point linear interpolation?](https://stackoverflow.com/a/30438865/2521214) piecewise is always an option – Spektre Jul 18 '19 at 08:10
  • Possible duplicate of [Finding the mathematical algorithm to which matches an input and output together](https://stackoverflow.com/questions/31466518/finding-the-mathematical-algorithm-to-which-matches-an-input-and-output-together) – Spektre Jul 18 '19 at 08:11

0 Answers0