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

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

• The first one looks like a particular case of Akra-Bazzi Do you need to deduce your problem from scratch? For the second one you could to a change of variable first $S(k)=T(2^k)$ and bounding other values of $T$ between values of $S$. On $S$ you can apply the master theorem. – plop Nov 25 '20 at 17:51
• @plop First I've never heard of Akra-Bazzi, second what do you mean in your second question?I've been asked to get $T(n)=\Theta(g(n))$ – convxy Nov 25 '20 at 17:55
• Now you have heard about it. My question is asking if you would be fine with just applying a theorem, or you would need to deduce your problem from simpler facts than that. – plop Nov 25 '20 at 19:54
• @plop yes I need to deduce it from simpler methods – convxy Nov 26 '20 at 4:52

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 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 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)$$

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 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 and $$Dn^2\int_{n/3}^{n}\frac{dx}{x^{p+1}}=4D\leq 1$$.

Assume that for all $$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)$$