Computational complexity of calculating the $n$th derivative of $f(x)=\exp\bigg(\frac{1}{\ln(x)}+\frac{1}{\ln(1-x)}\bigg)$?

Question

Computational complexity of calculating $$ f^{(n)}(x)? $$ where $f(x)=\exp\bigg(\frac{1}{\ln(x)}+\frac{1}{\ln(1-x)}\bigg)$

I don't know much about computational complexity but I do know that the derivatives just keep accumulating more and more mass.

I think the running time is exponential time. What's the fastest running time it can be calculated in?

Answer 1

It's not clear what you mean by 'calculated' here, but assuming that what you want is the expression for the derivative of your $f()$, then the size of the formula should only be polynomial — and I believe it should be possible to compute the coefficients in polynomial time. To be more specific: your function $f$ can be written as $g\circ h$, where $g(x)=e^x$ and $h(x)=(\ln x)^{-1}+(\ln (1-x))^{-1}$. To compute the $n$th derivative of a composition of functions, we can use the Faa di Bruno formula. I won't go into it in detail, but the relevant piece of discussion here is the form of the terms: each one is of the form $Cg^{(k)}\circ h(x)\cdot\prod_j\left(h^{(j)}(x)\right)^{m_j}$ for suitable $m_j$. Now, since your $g$ is the exponential, we have $g^{(k)}(x) = g(x)=e^x$ for all $k$; this means that all of the complexity is in the derivatives of $h$, and products of those derivatives.

Now, your $h(x)$ (that is, $(\ln x)^{-1}+(\ln (1-x))^{-1}$) is also a composite function, but because of its form we can say some pretty specific things about its derivatives; in particular, $h^{(j)}(x)$ will be a sum of terms of the form $Cx^a(\ln x)^b$ and terms of the form $D(1-x)^c(\ln (1-x))^d$ with $-j\lt a, c\leq 0$ and $-j-1\leq b, d\leq 1$. (You should be able to prove this by induction: the derivative of $x^a(\ln x)^b$ is $ax^{a-1}(\ln x)^b + bx^{a-1}(\ln x)^{b-1}$, and similarly with $x$ replaced by $1-x$.) But this means that every power of $h^{(j)}$ will be a sum of products of these terms; in other words, it'll be a sum of terms of the form $Cx^{a}(\ln x)^b(1-x)^c(\ln (1-x))^d$. In fact, if you analyze the Faa di Bruno formula carefully you should be able to convince yourself that the $n$th derivative of your original $f(x)$ will be $f(x)$ times a sum of terms of this form with $|a|, |b|, |c|, |d|$ $\leq n+1$.

Having this formula, it can also easily be proven directly by induction, by looking at the derivative of $x^{a}(\ln x)^b(1-x)^c(\ln (1-x))^d f(x)$ and noting that it's a sum of terms of this form, with the exponents changing by at most 1; this is the simplest way of tackling the problem, but I wanted to include the process that got me to this point.

But there can only be $O(n^4)$ terms of this form, and given a matrix $C_{abcd, n}$ of the coefficients for the $n$th derivative, we can compute the coefficients $C_{abcd, (n+1)}$ of the $(n+1)$th derivative using polynomially many operations; each $C_{abcd,(n+1)}$ will depend on a constant number of terms $C_{ijkl, n}$. So the total time to compute all the coefficients for the $n$th derivative of $f()$ is at worst $O(n^5)$.

Answer 2

The answer by Steven Stadnicki isn't quite right. For each term with exponents $(a,b,c,d)$, you get six terms in the next derivative:

• $(a-1,b,c,d)$
• $(a-1,b-1,c,d)$
• $(a,b,c-1,d)$
• $(a,b,c-1,d-1)$
• $(a-1,b-2,c,d)$
• $(a,b,c-1,d-2)$

The first four come from differentiating $x$, $\ln x$, $(1-x)$, $\ln (1-x)$ respectively. The last one comes from differentiating the exponential, which multiplies by $(-x^{-1}(\ln x)^{-2} + (1-x)^{-1}(\ln (1-x))^{-2})$. This means that $0 \ge b \ge 2a$ and $0 \ge d \ge 2c$. So there's four times as many as he thought.

But luckily, it's actually much better than he thought. Notice that the sum $a+c$ always decreases by one, so $-(a+c)=n$. That means the number of terms in the $n$-th derivative is only $O(n^3)$, and the total time is $O(n^4)$.

But we can do much better. Define $$g(x) = \exp\bigg( {1 \over {\ln x}} \bigg)$$ so $$f(x)= g(x) \cdot g(1-x)$$ By the General Leibniz rule, $$f^{(n)}(x) = \sum_{i=0}^n {n \choose i} (-1)^{n-i} g^{(i)}(x)g^{(n-i)}(1-x)$$

When you compute the derivatives of $g$, you only have the $x$ and $\ln x$ factors, so $g^{(n)}$ only has $O(n)$ terms, and the total time is $O(n^2)$.