Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

There are many expressions, which can be considered straight generalizations of others.

I'm motivated by values of integral expressions specifically, for example there is

$$\int_0^\infty e^{-a x^2}\,dx = \frac{1}{2} \sqrt \frac {\pi}{a},$$

and then

$$\int_0^\infty x^{2n} e^{-a x^2}\,dx = \frac{(2n)!}{n!\cdot 2^{2n+1}} \sqrt{\frac{\pi}{a^{2n+1}}},$$

which just evaluates to the former by setting $n=0$.

The integral

$$\int_0^\infty e^{-a x^2+c}\,dx = \frac{1}{2} \sqrt \frac {\pi}{a}e^{c}\,$$

would be another (cheap) generalization. It's itself closely related to

$$\int_{-\infty}^\infty e^{-(ax^2+bx+c)}\,dx = \sqrt{\frac{\pi}{a}}\exp\left(\frac{b^2-4ac}{4a}\right).$$

Now by the ordering of complexity classes, it seems to me that I can define a measure of how effectively distant generalizations of certain expressions are. Let's denote the right hand side of the initial expression by $f:=\frac{1}{2} \sqrt \frac {\pi}{a}$. Now I only have to compare the runtime of the "generalizations" $$g_f^1(n):=\frac{(2n)!}{n!\cdot 2^{2n+1}} \sqrt{\frac{\pi}{a^{2n+1}}}$$ on $n=0$, and $$g_f^2(c):=\frac{1}{2} \sqrt \frac {\pi}{a}e^{c}$$ on $c=0$.

(sidenote: In this case, the one involving only the exponential will be faster than the one involving the exponental and the factorials. Here I wonder: Is there a rule of thumb or a lookup list to guess or find out the complexities of such "simple functions". Something like your everyday, practical regular function hierarchy table or something like that?)

Okay, now say I have an expression $f$ and a generalization $g_f(n)$, which evaluates to $g_f(0)=f$. Furthermore I found a generalization of the generalization, $g_{g_f}(n,m)$ with $g_{g_f}(n,0)=g_f(n)$. This means $g_{g_f}(0,0)=f$ and I see this also implies I found another generalization $g_{g_f}(0,m)$ of $f$. (This function $g_{g_f}$ is fixed in the question, one can start from here on.)

There might be other pairs $(N,M)$ with $g_{g_f}(N,M)=f$. Is there a way to find this "kernel"? Given all these right values, there is an function $\hat M(N)$, giving familty $g_{g_f}(N,\hat M(N))$ parametrized by the single parameter $N$. This function must be more than a list of pairs right? After all, it comes from an analytic expression. So I guess it's kind of an implicit function for the family. How do the runtimes differ from $g_{g_f}(\hat N(M),M)$? - this essentially askes for the runtime relation between a function and its inverse.

And then given the values of $\{N\}$ for which $g_{g_f}(N,\hat M(N))=f$, can I now find a most efficient generalization of $f$ among these? I mean other than computing it, i.e. does the runtime relate to $\hat M(N)$? Is there any general information which says how the order of evaluation impacts the runtime of a code?

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.