If you want to make money online : Register now

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

, , No Comments
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$?

Asked By : Siddharth Thevaril

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/35525

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback