Solve the following recurrence-relations: $T(n)=5T(n/3)+T(2n/3)+1,T(n)=2T(\sqrt{n})+\log_2(n)$

Question

Solve the following recurrence-relations:
my attempet for the first one was doing upper bound and lower bound by changing for lower $6T(n/3)+1$ and for upper $6T(2n/3)+1$ but i didn't get the same order for $\Theta$ $T(n)=5T(n/3)+T(2n/3)+1,T(1)=c$

$T(n)=2T(\sqrt{n})+\log_2(n),T(4)=2$
I'm not sure if I solved this right but:
setting $y(n)=T(2^n)$ we get
$y(n)=2T(\sqrt{2^n})+\log_2(2^n)=2y(n/2)+n$ using the master's theorem we get that $y(n)=\Theta(nlogn)$ and therefore $T(n)=\Theta(log(n)loglog(n))$ And for the first recurrence i still don't know

Answer 1

Now that we know the answer, we could simplify the proof.

Let's prove that $$T(n)\in\Theta\left(n^2\right)$$

Define $k=k_n$, index of $n$ in base $3/2$, to be the smallest $k$ such that $n/(3/2)^k<1$.

---

Upper bound:

Assume that $C$ is very large such that $T(1)\leq C=C\cdot1^2$, $1-3C<-C/2$, and that for all $k<K$ and all $m$ with index $k$ we have $$T(m)\leq C(m^2-1/2)$$

Note: We are going to use the $-1/2$ to carry out the induction as it was done in the other answer.

Let $n$ be of index $K$. Then $n/3$ and $2n/3$ are of index smaller than $K$. It follows that

$$\begin{align}T(n)&=5T(n/3)+T(2n/3)+1\\ &\leq 5C(n/3)^2-5C/2+C(2n/3)^2-C/2+1\\ &=Cn^2\left(5/3^2+(2/3)^2\right)+1-3C\\ &=Cn^2+1-3C\\ &\leq Cn^2-C/2\\ &=C(n^2-1/2)\end{align}$$

---

Lower bound:

Assume that $D$ is such that $D>0$, $T(1)\geq D\cdot 1^2=D$, $1-3D\geq -D/2$, and that for every $k<K$ and $m$ of index $k$ we have $$D(m^2-1/2)\leq T(m)$$

Let $n$ be of index $K$. Then $n/3$ and $2n/3$ are of index smaller than $K$. Therefore,

$$\begin{align} T(n)&=5T(n/3)+T(2n/3)+1\\ &\geq 5D((n/2)^2-1/2)+D((2n/3)^2-1/2)+1\\ &=Dn^2\left(5/3^2+1/(3/2)^2\right)-5D/2-D/2+1\\ &=Dn^2+1-3D\\ &\geq D\left(n^2-1/2\right) \end{align}$$

---

By induction we have proven that for all $n$ we have $$D(n^2-1/2)\leq T(n)\leq C(n^2-1/2)$$

Therefore, $$T\in \Theta(n^2-1/2)=\Theta(n^2)$$

Answer 2

You would just need to follow Akra-Bazzi's argument for your particular case.

Let's prove that $$T(n)\in\Theta\left(n^2\left(\frac{3}{2}-\frac{1}{2n^2}\right)\right)$$

Here $$\frac{3}{2}-\frac{1}{2n^2}=1+\int_{1}^{n}\frac{dx}{x^{2+1}}$$

First let $b=\min(3,\frac{3}{2})=\frac{3}{2}$. Let $k_n$ be the smallest positive integer such that $n/b^{k_n}<1$. Call this $k_n$ the index of $n$ base $b$.

Let $p$ be the solution to $5/3^p+1/(3/2)^p=1$. This is, $$p=2$$

---

Upper bound:

Take $C$ such that $T(1)\leq C$ and $Cn^p\int_{2n/3}^{n}\frac{dx}{x^{p+1}}=5C/8\geq 1$.

Then $T(1)\leq C=Cm^2\left(1+\int_{1}^{m}\frac{dx}{x^{p+1}}\right)|_{m=1}$

Assume that for all $k<K$ and all $m$ of index $k$ we have

$$T(m)\leq Cm^2\left(1+\int_{1}^{m}\frac{dx}{x^p+1}\right)$$

Let $n$ be of index $K$. Then $n/3$ and $2n/3$ have index smaller than $K$. Using the assumption we have that

$$\begin{align}T(n)&=5T(n/3)+T(2n/3)+1\\ &\leq 5C(n/3)^p\left(1+\int_{1}^{n/3}\frac{dx}{x^{p+1}}\right)+C(2n/3)^p\left(1+\int_{1}^{2n/3}\frac{dx}{x^{p+1}}\right)+1\\ &\leq5C(n/3)^p\left(1+\int_{1}^{\mathbf{2}n/3}\frac{dx}{x^{p+1}}\right)+C(2n/3)^p\left(1+\int_{1}^{2n/3}\frac{dx}{x^{p+1}}\right)+1\\ &=C\left(5/3^p+1/(3/2)^p\right)n^p\left(1+\int_{1}^{2n/3}\frac{dx}{x^{p+1}}\right)+1\\ &=Cn^p\left(1+\int_{1}^{2n/3}\frac{dx}{x^{p+1}}\right)+1\\ &\leq Cn^p\left(1+\int_{1}^{n}\frac{dx}{x^{p+1}}\right)\end{align}$$

So, by induction on the index of $n$ we get that for all $n\geq1$

$$T(n)\leq Cn^p\left(1+\int_{1}^{n}\frac{dx}{x^{p+1}}\right)=Cn^2\left(\frac{3}{2}-\frac{1}{2n^2}\right)$$

---

Lower bound:

Now let's prove the bound from below. It is a very similar argument.

Take $D$ such that $0<D\leq T(1)$ and $Dn^2\int_{n/3}^{n}\frac{dx}{x^{p+1}}=4D\leq 1$.

Assume that for all $k<K$ and all $m$ of index $k$ we have that $$Dm^p\left(1+\int_{1}^{m}\frac{dx}{x^{p+1}}\right)\leq T(m)$$.

Let $n$ be of index $K$. Then $n/3$ and $2n/3$ are of index smaller than $K$. Using the assumption we have that

$$\begin{align}T(n)&=5T(n/3)+T(2n/3)+1\\ &\geq5D(n/3)^p\left(1+\int_{1}^{n/3}\frac{dx}{x^{p+1}}\right)+D(2n/3)^p\left(1+\int_{1}^{2n/3}\frac{dx}{x^{p+1}}\right)+1\\ &\geq5D(n/3)^p\left(1+\int_{1}^{n/3}\frac{dx}{x^{p+1}}\right)+D(2n/3)^p\left(1+\int_{1}^{n/3}\frac{dx}{x^{p+1}}\right)+1\\ &=(5/(3^p)+1/(3/2)^p)Dn^p\left(1+\int_{1}^{n/3}\frac{dx}{x^{p+1}}\right)+1\\ &=Dn^{p}\left(1+\int_{1}^{n/3}\frac{dx}{x^{p+1}}\right)+1\\ &\geq Dn^p\left(1+\int_{1}^{n}\frac{dx}{x^{p+1}}\right)\end{align}$$

Hence, for all $n\geq1$ $$Dn^2\left(\frac{3}{2}-\frac{1}{2n^2}\right)=Dn^p\left(1+\int_{1}^{n}\frac{dx}{x^{p+1}}\right)\leq T(n)$$