If you want to make money online : Register now

# [Solved]: What kind of recurrence relations has p < 0?

, ,
Problem Detail:

By the master method, $T(n) = aT(\frac {n}{b})+\Theta(n^k\log^pn)$ where $p$ is real.

I know $\log^4n=\log(\log(\log(\log n)))$ but how do you calculate something like $\log^pn$ where $p<0$?

#### Answered By : Yuval Filmus

As Rick Decker mentions, in this context $\log^p n = (\log n)^p$, and so $p$ can be an arbitrary real number. If you wanted to denote composition, you would use $\log^{(p)} n$ (which in other contexts signifies the $p$th derivative!). In that case, when $p$ is a negative integer, you just need to use the inverse of $\log$, namely $\exp$: \begin{align*} \log^{(2)} x &= \log\log x \\ \log^{(1)} x &= \log x \\ \log^{(0)} x &= x \\ \log^{(-1)} x &= e^x \\ \log^{(-2)} x &= e^{e^x} \end{align*} This definition ensures that $\log^{(a)} \log^{(b)} x = \log^{(a+b)} x$ for all integers $a,b$. The natural domain of this definition is integer $p$, though it can probably be extended for fractional $p$ in such a way that the equation above still holds.