1
$\begingroup$

Let's consider these four function types : Polynomial, Exponential, Logarithmic and Trigonometric.

Considering that both input and output values are floating point numbers.

How do they rank in terms of time complexity (of computing an output value for a given input value) ?

$\endgroup$
  • 4
    $\begingroup$ This is a question that doesn't have a single answer. It depends on (1) how a compiler would translate something like $y=sin(x)$ into machine language and that would depend on (2) what the machine language would have built in to deal with the result. I don't know of any machine language that is equipped to deal with trig functions, but I can imagine a special-purpose computer that has a special trig processor, for example. By the way, welcome to the site! Don't be upset by the possibility that your question might be closed as too broad. $\endgroup$ – Rick Decker Jan 20 '16 at 1:59
  • 1
    $\begingroup$ 1. What are your thoughts? What analysis have you done? Have you tried analyzing the running time of any of these function types? What did you come up with? 2. It's going to be difficult to answer this, as the running time of evaluating a polynomial depends on the degree of the polynomial. For a high-degree polynomial it might be very slow (much slower than the other three); for a low-degree polynomial it might be very fast. $\endgroup$ – D.W. Jan 20 '16 at 5:22
  • 1
    $\begingroup$ Usually when speaking of complexity in CS, there is an input size as a parameter. Although for polynomial I can see the degree used as such, for the other functions I wonder. $\endgroup$ – AProgrammer Jan 20 '16 at 10:35
  • $\begingroup$ @AProgrammer: you are quite right. In this case, one could use the input argument as the complexity parameter, and the answer is essentially $O(1)$ ! $\endgroup$ – Yves Daoust Jan 20 '16 at 14:43
  • $\begingroup$ Do you want an answer from theory or from practice ? These would be very different. $\endgroup$ – Yves Daoust Jan 20 '16 at 14:45
1
$\begingroup$

To evaluate polynomial you use Horners scheme, or if you do not know how to compute it, still straightforward naive approach works. It depends on "how big" is this polynomial...

For logarithm and exponent you could use BKM and for trigonometric functions CORDIC.
So ranking by time polynomial is the fastest, and the rest is equally time consuming.
It is hard to tell apart, as basically the same algorithm can compute all these functions.

Using floating point numbers (so inexact results are obvious) the time complexity of special functions is $O(1)$, because underneath you have constant number of rounds no matter what the input was.
Number of iterations is fixed for given precision, so it does not depend on particular input (although angle reduction is time consuming for huge input value).
Polynomial evaluation is $O(n)$ in number of given coefficients using Horner, otherwise it is $O(n^2)$.

$\endgroup$
  • 2
    $\begingroup$ I believe the question is asking about evaluating functions, not solving equations involving those functions. $\endgroup$ – David Richerby Jan 20 '16 at 7:28
  • 1
    $\begingroup$ @DavidRicherby and to the upvoters: you should read past the first two words. $\endgroup$ – Yves Daoust Jan 20 '16 at 14:39
  • $\begingroup$ @DavidRicherby I belive that solving in given point is evaluating. Edited, but still Horner Scheme, CORDIC, BKM - this are evaluation methods I belive. $\endgroup$ – Evil Jan 20 '16 at 15:18
0
$\begingroup$

If by "computer" you mean e.g. a bog-standard PC, polynomials are harder to compute. The basic elementary functions (square root, sin, cos, natural logarithm, exponential) are computed in hardware, by specialized instructions.

To compute a polynomial, the best technique is Horner's method. It can be shown optimal if the coefficients aren't known beforehand.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.