# How to solve $T(n) = 2 T(\frac{n}{8}) + \Theta(\sqrt{n})$

I'm tasked to give the best possible asymptotic bounds for the following recurrence:

$$T(n) = 2 T\left( \frac n 8 \right) + \Theta(\sqrt{n})$$

I got the following using the iterative method:

\begin{align} T(n) & = 2 T \left( \frac n 8 \right) + \Theta(\sqrt{n}) \\ & = 2^2 T \left( \frac n {8^2} \right) + \Theta(\sqrt{n}) \\ & \,\,\,\vdots \\ & = 2^k + \Theta(\sqrt{n}) \end{align}

By setting $k = \log_8 (n)$ we get:

$$= 2 ^{\frac{\log_2(n)}{\log_2(8)}} + \Theta(\sqrt{n})$$

$$= \sqrt{2^{\log_2(n)}} + \Theta(\sqrt{n})$$

$$= \Theta(\sqrt{n})$$

Is this correct ?

Thanks for any answers.

## 1 Answer

The strictest proof goes like this. Following the definition of $\Theta(\sqrt{n})$, there exists two constants $C_1$ and $C_2$, such that for all sufficiently large $n\geq n_0$, where $n_0$ is a constant (may depend on $C_1,C_2$)

$$C_1\sqrt{n}\leq T(n)-2T(\frac{n}{8})\leq C_2\sqrt{n}.$$

Then multiply everybody by $2$ and replace $n$ by $n/8$ to get

$$2C_1\sqrt{\frac{n}{8}}\leq 2T(\frac{n}{8})-4T(\frac{n}{8^2})\leq 2C_2\sqrt{\frac{n}{8}}.$$

Notice that $8=2^3$ is the critical case. So we have

$$C_1\sqrt{n}\leq 2T(\frac{n}{8})-4T(\frac{n}{8^2})\leq C_2\sqrt{n},$$ $$C_1\sqrt{n}\leq 4T(\frac{n}{8^2})-8T(\frac{n}{8^3})\leq C_2\sqrt{n},$$ $$\cdots\,\cdots\;\cdots\,\cdots\;\cdots\,\cdots\;\cdots\,\cdots\;$$ $$C_1\sqrt{n}\leq 2^kT(\frac{n}{8^k})-2^{k+1}T(\frac{n}{8^{k+1}})\leq C_2\sqrt{n}.$$

We can do this all the way until $\frac{n}{8^k}\geq n_0$ is unsatisfied, i.e., $k\leq\log_8\frac{n}{n_0}=\frac{1}{3}\,\log_2\frac{n}{n_0}$. Adding the inequalities up, we get

$$kC_1\sqrt{n}\leq T(n)-2^{k+1}T(\frac{n}{8^{k+1}})\leq kC_2\sqrt{n}.$$

Therefore, the complexity is given by \begin{align} T(n)&=\Theta(2^{k+1}T(\frac{n_0}{8}))+\Theta(k\sqrt{n})\\ &=\Theta(\sqrt{n})+\Theta(\sqrt{n}\log_2n)=\Theta(\sqrt{n}\log_2n). \end{align} So you missed a factor of $\,\log_2n\,$ by assuming $\,\Theta(\sqrt{n})+\cdots+\Theta(\sqrt{n})=\Theta(\sqrt{n})$ ($\times$). We need to be careful when adding infinite terms.