0
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – plop
    Nov 25, 2020 at 17:51
  • $\begingroup$ @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))$ $\endgroup$
    – convxy
    Nov 25, 2020 at 17:55
  • $\begingroup$ 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. $\endgroup$
    – plop
    Nov 25, 2020 at 19:54
  • $\begingroup$ @plop yes I need to deduce it from simpler methods $\endgroup$
    – convxy
    Nov 26, 2020 at 4:52

2 Answers 2

1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.