# What kind of recurrence relations has p < 0?

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$?

• Customarily, $\log^pn$ denotes $(\log n)^p$, so for example, $\log^{-2}n=1/(\log n)^2$. For the iterated log, like $\log(\log n)$, assuming you're not dealing with complex numbers, expressions like $\log(\log 1)$ are simply undefined. – Rick Decker Dec 19 '14 at 16:14

## 1 Answer

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.