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.


1 Answer 1


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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .