<s>[INST] How to solve $ T(n) = 2 T(\frac{n}{8}) + \Theta(\sqrt[3]{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[3]{n}) $$
I got the following using the iterative method:
\begin{align} T(n) & = 2  T \left( \frac n 8 \right) + \Theta(\sqrt[3]{n}) \\
& = 2^2 T \left( \frac n {8^2} \right) + \Theta(\sqrt[3]{n}) \\
& \,\,\,\vdots \\
& = 2^k + \Theta(\sqrt[3]{n})
\end{align}
By setting $ k = \log_8 (n) $ we get:
$$ = 2 ^{\frac{\log_2(n)}{\log_2(8)}} + \Theta(\sqrt[3]{n}) $$
$$ = \sqrt[3]{2^{\log_2(n)}} + \Theta(\sqrt[3]{n}) $$
$$ = \Theta(\sqrt[3]{n}) $$
Is this correct ?
Thanks for any answers.
 [/INST] The strictest proof goes like this. Following the definition of $\Theta(\sqrt[3]{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[3]{n}\leq T(n)-2T(\frac{n}{8})\leq C_2\sqrt[3]{n}.$$
Then multiply everybody by $2$ and replace $n$ by $n/8$ to get
$$2C_1\sqrt[3]{\frac{n}{8}}\leq 2T(\frac{n}{8})-4T(\frac{n}{8^2})\leq 2C_2\sqrt[3]{\frac{n}{8}}.$$
Notice that $8=2^3$ is the critical case. So we have
$$C_1\sqrt[3]{n}\leq 2T(\frac{n}{8})-4T(\frac{n}{8^2})\leq C_2\sqrt[3]{n},$$
$$C_1\sqrt[3]{n}\leq 4T(\frac{n}{8^2})-8T(\frac{n}{8^3})\leq C_2\sqrt[3]{n},$$
$$\cdots\,\cdots\;\cdots\,\cdots\;\cdots\,\cdots\;\cdots\,\cdots\;$$
$$C_1\sqrt[3]{n}\leq 2^kT(\frac{n}{8^k})-2^{k+1}T(\frac{n}{8^{k+1}})\leq C_2\sqrt[3]{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[3]{n}\leq T(n)-2^{k+1}T(\frac{n}{8^{k+1}})\leq kC_2\sqrt[3]{n}.$$
Therefore, the complexity is given by
\begin{align}
T(n)&=\Theta(2^{k+1}T(\frac{n_0}{8}))+\Theta(k\sqrt[3]{n})\\
&=\Theta(\sqrt[3]{n})+\Theta(\sqrt[3]{n}\log_2n)=\Theta(\sqrt[3]{n}\log_2n).
\end{align}
So you missed a factor of $\,\log_2n\,$ by assuming $\,\Theta(\sqrt[3]{n})+\cdots+\Theta(\sqrt[3]{n})=\Theta(\sqrt[3]{n})$ ($\times$). We need to be careful when adding infinite terms.
</s>