Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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.