How to simplify the summation of a recurrence relation

143 Views Asked by At

After solving the recurrence relation

$$T(n) = 3T(\frac{n}{3}) + n\log(n)$$

I get following equation

$$T(n)=3kT(\frac{n}{3k})+ n\log(n) + n\log(\frac{n}{3}) + n\log(\frac{n}{3^2})+\dots+n\log(\frac{n}{3^k})$$

I don't know how to simplify the summation and how to know the asymptotic function?

2

There are 2 best solutions below

0
On

Let $n=3^k$. We have,

$T(n)=3^kT(\frac{n}{3^k})+ n\log(n) + n\log(\frac{n}{3}) + n\log(\frac{n}{3^2})+\dots+n\log(\frac{n}{3^k})$

$=3^k.T(1)+n\log\left(n.\frac{n}{3^1}.\frac{n}{3^2}\ldots.\frac{n}{3^k}\right)$

$=3^k.1+n\log\left(n.\frac{n^k}{3^{1+2+\ldots+k}}\right)$ (since $T(1)=1$)

$=3^k+n\log\left(\frac{n^{k+1}}{3^{1+2+\ldots+k}}\right)$

$=3^k+n\log\left(\frac{(3^k)^{k+1}}{3^{k(k+1)/2}}\right)$

$=3^k+n\log\left(\frac{3^{k(k+1)}}{3^{k(k+1)/2}}\right)$

$=3^k+3^k\log\left(3^{k(k+1)/2}\right)$

$=3^k+3^k.k(k+1)/2.\log3$

$=3^k+\Theta(3^k.k^2)$

$=\Theta(3^k.k^2)$

$=\Theta(n.(\log n)^2)$ (since $n=3^k$)

Or use Master theorem:

$T(n) = 3T(\frac{n}{3}) + n\log(n)$, here $c_{crit}=\log_b a = \log_3 3 = 1$, $k=1$, hence, we have,

$T(n) = \Theta(n^{c_{crit}}\log^{k+1}n)=\Theta(n\log^2 n)$

0
On

Assuming $\log n = \ln n$ we have

$$ T\left(3^{\log_3 n}\right)=3T\left(3^{\log_3 \left(\frac n3\right)}\right)+n\frac{\log_3 n}{\log_3 e} $$

now calling $\mathcal{T}(\cdot)=T\left(3^{(\cdot)}\right)$ and $z = \log_3 n$ we follow with the recurrence

$$ \mathcal{T}(z)= 3 \mathcal{T}(z-1)+z3^z c_0 $$

with solution

$$ \mathcal{T}(z)= 3^{z-1}c_1+z(z+1)3^z\frac{c_0}{2} $$

and now going backwards with $z = \log_3 n$ we arrive at

$$ T(n) = \frac n3 c_1 +n(\log_3 n) (1+\log_3 n)\frac {c_0}{2} $$

NOTE

The recurrence $\mathcal{T}(z)= 3 \mathcal{T}(z-1)+z3^z c_0 $ is linear so the solution can be composed as $\mathcal{T}(z)=\mathcal{T}_h(z)+\mathcal{T}_p(z)$. The homogeneous solution is direct

$$ \mathcal{T}_h(z) = 3^{z-1}c_1 $$

now taking as particular $\mathcal{T}_p(z) = 3^{z-1}c_1(z)$ and substituting into the complete recurrence we get

$$ c_1(z) = c_1(z-1)+3z c_0 $$

hence

$$ c_1(z) = \frac 32z(z+1)c_0 $$

etc.