$T(n)=4T(n/3)+n\log_2(n)$

Question

I was wondering if i could find a closed form for this function:
$$T(n)=4T(n/3)+n\log_2(n) \text{ for $ n\in \mathbb N$}$$ $$\text{ & }T(0)=1$$ or at least some function $g$ s.t $T(n)=Θ\big(g(n) \big)$,
(I've tried Master theorem and it does not work here).
any ideas?

EDIT:$\text{ it turns out that: $\bbox[1px,border:1px solid red] {T(n)=Θ\big( n^{\log_3(4)} \big)}$}$

By using the strong version of Master theorem:

$$ \bbox[7px,border:2px solid red] {\text{MASTER THEOREM}}: $$

$$T(n)=aT(n/b)+f(n).$$ $$\bbox[1px,border:1px solid green] {a\ge 1,b>1,f(n)=Θ\big( n^k\cdot \log^p(n)\big)}$$ $$\text{CASE 1}:$$

$$ \text{if } \log_b(a)>k\text{ then: }\quad \bbox[1px,border:1px solid black] {T(n)=Θ\big( n^{\log_b(a)}\big)} $$

---

$$\text{CASE 2}:$$

$$\text{if } \log_b(a)=k:\begin{cases} \text{if $p>-1:\quad \bbox[1px,border:1px solid black] {T(n)=Θ\big( n^k\cdot \log^{p+1}(n)\big)}$} \\ \text{if $p=-1:\quad \bbox[1px,border:1px solid black] {T(n)=Θ\big( n^k\cdot \log\big( \log(n)\big)\big)} $ }\\ \text{if $p<-1:\quad \bbox[1px,border:1.5px solid black] {T(n)=Θ\big( n^k\big)}$ }\\ \end{cases} $$

---

$$\text{CASE 3}:$$

$$\text{if $\log_b(a)<k:\begin{cases} \text{if $p\ge 0:\quad \bbox[1px,border:1px solid black] {T(n)=Θ\big( n^k\cdot\log^p(n)\big)} $} \\ \text{if $p<0:\quad \bbox[0.5px,border:1px solid black] {T(n)=\mathcal O \big( n^k\big)} $} \end{cases}$}$$

---

Answer 1

Note that the sequence $T(3x), T(3^{2}x), T(3^{3}x), ...$ with $3\nmid x$ can be derived if and only if $T(x)$ is known. (In other words, all 'chains' like this are independent.) Thus, for all values of $T(n)$ to be known, all initial values $T(n)$ with $3\nmid n$ must be specified. In fact, $no$ values of $T(n)$ other than $T(0)$ can be derived right now because $\frac{0}{3} = 0$. We cannot even use continuity conditions because of the domain restriction to natural numbers. So, $\boxed{\text{No, we cannot derive a closed form for }T(n).}$

I will work on this under the condition that $n\in\mathbb{R}$ and that $T$ is continuous, but I do not think I will get very far.

Answer 2

I am sharing my calculations with hope to be useful. Taking $n=3^k$ we have $$T(n)=4\left( \frac{n}{3} \right)+n\log n = 4\left[4T\left( \frac{n}{3^2}\right) + \frac{n}{3}\log \frac{n}{3}\right]+n\log n = \\ = 4^2T\left( \frac{n}{3^2}\right)+4 \frac{n}{3}\log \frac{n}{3} +n\log n=\\ =4^2\left[ 4T\left( \frac{n}{3^3}\right) + \frac{n}{3^2}\log \frac{n}{3^2} \right] +4 \frac{n}{3}\log \frac{n}{3} +n\log n=\\ = 4^3T\left( \frac{n}{3^3}\right)+4^2\frac{n}{3^2}\log \frac{n}{3^2}+4 \frac{n}{3}\log \frac{n}{3} +n\log n = \\ = \cdots =\\ =4^kT(1)+4^{k-1}\frac{n}{3^{k-1}}\log \frac{n}{3^{k-1}}+\cdots+4 \frac{n}{3}\log \frac{n}{3} +n\log n$$ Now we can take some rough estimation, for example $T(n) \in O(n\log_3 n4^{\log_3 n})$, but I don't know how convenient it is for you.

Answer 3

This might not be what you're looking for, but there's always the method of power series.

Let $T(x)=\sum_{k\ge0}a_kx^k$, so that $$\sum_{k\ge0}\left(1-4/3^k\right)a_kx^k=-\frac{1}{\log2}+\frac{x}{\log2}+\frac{1}{\log2}\sum_{k\ge2}\frac{(-1)^k(x-1)^k}{k(k-1)}.$$ Since $v>u\Rightarrow{u\choose v}=0$, we have from the binomial theorem that $$(x-1)^k=\sum_{r\ge0}(-1)^{k-r}{k\choose r}x^r,$$ and thus $$\sum_{k\ge0}\left(1-4/3^k\right)a_kx^k=-\frac{1}{\log2}+\frac{x}{\log2}+\frac{1}{\log2}\sum_{r\ge0}x^r\underbrace{\sum_{k\ge2}\frac{(-1)^k}{k(k-1)}{k\choose r}}_{\alpha_{r}}.$$ This is $$\sum_{k\ge0}\left(1-4/3^k\right)a_kx^k=2-\frac2{\log2}+\left(1+\frac1{\log2}\right)x+\sum_{k\ge2}\frac{\alpha_k}{\log2}x^k,\qquad |x-1|<1.$$ Therefore $$\begin{align} a_0&=\frac13\left(\frac1{\log2}-1\right),\\ a_1&=-3\left(1+\frac1{\log2}\right),\\ a_k&=\frac{3^k}{(3^k-4)\log2}\sum_{n\ge2}\frac{(-1)^n}{n(n-1)}{n\choose k},\qquad k\ge2. \end{align} $$ This being the case, I highly doubt there is a closed form.