2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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