solving recurrence equations and get complexity T(n)...

483 Views Asked by At

I am trying to understand how to solve these recurrence equations but for those specific equations I didn't find any solution yet. what is the complexity of each equation?

\begin{align} T(n) &= 9T(n/2) + n^2 \log n \\ T(n) &= 12T(n/3) + n^2 \\ T(n) &= 25T(n/5) + n^2 \log^2 n \\ T(n) &= T(n-1) + n/\log n \\ T(n) &= T(\sqrt{n}) + 5n \end{align}

1

There are 1 best solutions below

0
On BEST ANSWER

If you only want asymptotic behaviour then at least the first three are direct application of the master theorem.

With a little courage, you can also get closed formula.

Sample #$4$

$T(n)=T(n-1)+\dfrac n{\ln(n)}$

By telescoping this, you get $T(n)-T(2)=\sum\limits_{k=2}^n \dfrac k{\ln(k)}$

Thus $T(n)\sim \operatorname{Li}(n^2)=\Theta\left(\dfrac{n^2}{\ln(n)}\right)$

Sample #$2$

$T(n)=12\,T(\frac n3)+n^2$

Let search a geometric relation for $\quad U(n)=12\dfrac{T(n)}{n}+an$

$U(3n)=\dfrac 4n\left(T(3n)\right)+3an=\dfrac 4n\left(12T(n)+9n^2\right)+3an=4\left(12\dfrac{T(n)}n+\left(9+\dfrac{3a}{4}\right)n\right)$

When $9+\dfrac{3a}4=a\iff a=36\quad$ then $\quad U(3n)=4\,U(n)$

We get $U(n)=C\,n^{\frac{\ln(4)}{\ln(3)}}$

So $T(n)=\dfrac n{12}\left(C\,n^{\frac{\ln(4)}{\ln(3)}}-36n\right)$

Since $\dfrac{\ln(4)}{\ln(3)}\approx 1.26>1$ then $T(n)\sim \frac C{12}n^{\frac{\ln(4)}{\ln(3)}+1}=\Theta(n^{2.26})$

You notice that eventually the (exact) term in $36n$ is negligible, thus we get the equivalent directly with the master theorem.

Sample #$1$

$T(n)=9\,T(\frac n2)+n^2\ln(n)$

The same principle apply, but since $[X^2\ln(X)]_{X=2n}=n^2\ln(2n)=n^2\ln(n)+n^2\ln(2)$

We will search for $U(n)=9\,\dfrac{T(n)}n+a\,n\ln(n)+b\,n\ln(2)$

I let you do the calculation we end up with $\begin{cases} 18+2a=\frac 92 a\\18+2a+2b=\frac 92 b\end{cases}\iff\begin{cases}a=\frac{36}5\\b=\frac{324}{25}\end{cases}$

Eventually $U(2n)=\frac 92 U(n)\iff U(n)=C\,n^{\frac{\ln(9)}{\ln(2)}-1}$

But again since $\frac{\ln(9)}{\ln(2)}-1\approx 2.17$ then the terms in $a$ and $b$ are negligible and $T(n)=\Theta(n^{3.17})$

Sample #$3$

This is similar to cases $1$ and $2$.

Sample #$5$

Hint: set $U(p)=T(2^p)$ then $U(p)=U(\frac p2)+5\times 2^p$