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

  • 3
    $\begingroup$ 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. $\endgroup$ – Rick Decker Dec 19 '14 at 16:14

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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.