0
$\begingroup$

To make my question more concrete, here is an example I am stuck on.

I want to prove that $T(n) = 8T(\frac{n}{2}) + n^3$ is asymptotic bound by $n^3\log(n)$ using the substution method. That is $T(n)$ is $\Theta(n^3\log(n))$, so both $O(n^3\log(n))$ and $\Omega(n^3 \log(n))$.

We know $T(n) = \Theta(n^3 \log(n)) \Leftrightarrow \exists c_1, c_2, n_0 > 0: \forall n > n_0 . c_1 n^3 \log(n) \leq T(n) \leq c_2 n^3 \log(n)$.

Given that I assume the proof should go somewhat as follows:

To show: $\exists c_1, c_2, n_0 > 0: \forall n > n_0 . c_1 n^3 \log(n) \leq T(n) \leq c_2 n^3 \log(n)$

To do this we can use strong induction.

Let $P(n)$ be $c_1 n^3 \log(n) \leq T(n) \leq c_2 n^3 \log(n)$.

Take $n$ to be an arbitrary natural number.

Induction hypothesis: $P(1),P(2),...,P(n-1)$. And notably, $P(\frac{n}{2})$.

It seems fairly straight forward to show the right-hand side of $P(n)$, that is that $\forall n > n_0 . T(n) \leq c_2 n^3 \log(n)$.

It follows that (taking $\log$ to be in base $2$):

$$ \begin{align*} P(\frac{n}{2}) &\Leftrightarrow T(\frac{n}{2}) \leq c_2 (\frac{n}{2})^3\log(\frac{n}{2}) \\ &\Leftrightarrow 8T(\frac{n}{2}) + n^3 \leq 8c_2 (\frac{n}{2})^3 \log(\frac{n}{2}) + n^3 \\ & \Leftrightarrow T(n) \leq 8c_2\frac{n^3}{8}(\log(n) - log(2)) + n^3 \\ & \Leftrightarrow T(n) \leq c_2n^3\log(n) + n^3 - c_2n^3log(2) \\ & \Leftrightarrow T(n) \leq c_2n^3\log(n) + n^3 - c_2n^3 \leq c_2n^3\log(n) \ \text{ (if $c_2 \geq 1$)} \end{align*} $$

So we have $P(n)$.

And as such $\exists c_2, n_0 > 0: \forall n > n_0 . T(n) \leq c_2 n^3 \log(n)$.

My problem:

So we have shown that $T(n) = O(n^3 \log (n))$ but not yet that $T(n) = \Omega(n^3 \log (n))$ which is also required to have $T(n) = \Theta(n^3 \log(n))$.

And that is what I am not sure how to go about showing — the left-hand side of $P(n)$, that is that given $P(\frac{n}{2})$, we have $c_2 n^3 \log(n) \leq T(n)$.

Can someone provide some insight into how to approach this?

$\endgroup$
  • 1
    $\begingroup$ The variable $n$ is not a free variable in "$\exists c_1, c_2, n_0 > 0: \forall n > n_0 . c_1 n^3 \log(n) \leq T(n) \leq c_2 n^3 \log(n)$". That is, $P(n)$ does not make sense. $\endgroup$ – Apass.Jack Apr 2 at 18:10
  • $\begingroup$ I am confused by the last line of your induction. Specifically I'm not sure how you got $\tfrac{n^3}{\log}(n)$ or what it really means. Is that what you meant to type or is there a typo somewhere? $\endgroup$ – ryan Apr 3 at 2:20
  • $\begingroup$ I am guessing it is just a typo from when you cancelled out the 8's. Anyway, your upper bound proof is not quite right. You claim $T(n) \leq c_2 n^3 \log n$, but then you "prove" $T(n) \leq c_2 n^3 \log n + n^3$. Your claim does not match what you show, thus your induction hypothesis does not hold. You can fix this by setting $c_2 = 1$ however. Also, with a base case of $T(2) = 8$ you can prove precise equality, that $T(n) = n^3 \log_2 n$ by induction, no need to mess with upper or lower bounds. $\endgroup$ – ryan Apr 3 at 2:42
  • $\begingroup$ @Apass.Jack I have updated the question to address this issue. Please let me know if the way I have written it out now makes mathematical sense and is logically correct. $\endgroup$ – Pabi Apr 3 at 12:17
  • $\begingroup$ @ryan you are right, that is, in fact, a typo. I have updated the question to fix this issue. I have also updated the question to address the problem of not properly proving $T(n) \leq c_2 n^3 \log n + n^3$. $\endgroup$ – Pabi Apr 3 at 12:18
1
$\begingroup$

You can prove precise equality for your recurrence. I'm going to assume the base case:

$$T(n) = \begin{cases} 8 & n = 2\\ 8T\left(\tfrac{n}{2}\right) + n^3 & n > 2\\ \end{cases}$$

Claim: $T(n) = n^3 \log_2 n$

Base Case ($n = 2$): $T(2) = 8 = 2^3 \log_2 2 = 8$

Inductive Case ($n > 2$):

$$\begin{align*} T(n) & = 8T\left(\tfrac{n}{2}\right) + n^3\\ & = 8\left(\tfrac{n^3}{8} \log_2 \tfrac{n}{2}\right) + n^3\\ & = n^3 \log_2 \tfrac{n}{2} + n^3\\ & = n^3 \log_2 n - n^3 \log_2 2 + n^3\\ & = n^3 \log_2 n - n^3 + n^3\\ & = n^3 \log_2 n & \square \end{align*}$$

Thus $T(n) = n^3 \log_2 n \implies T(n) = O(n^3 \log n)$. No need to mess with lower or upper bounds.


However, in general this equality might not be the correct solution. Sometimes you will need to add lower order terms to get the equality or inequality to hold. A general approach to determine the lower order terms is as follows:

If we have:

$$T(n) = \begin{cases} f(b) & n = b\\ aT(n/b) + f(n) & n > b \end{cases}$$

We first assume $n = b^k$ for some $k$. Next we can turn this into a summation:

$$\begin{align*} T(n) & = aT(n/b) + f(n)\\ & = a(aT(n/b^2) + f(n/b)) + f(n)\\ & = a^2T(n/b^2) + af(n/b) + f(n)\\ & \vdots\\ & = \sum_{i = 0}^{\log_b n - 1} a^{i} f\left( \frac{n}{b^i}\right) \end{align*}$$

Then if you can find a closed form for this sum, we can easily prove equality by induction (e.g. substitution method) with proper constants. Here is your example again:

$$\begin{align*} T(n) & = 8T\left(\tfrac{n}{2}\right) + n^3\\ & = \sum_{i = 0}^{\log_2 n - 1} 8^{i} \left( \frac{n}{2^i}\right)^3\\ & = \sum_{i = 0}^{\log_2 n - 1} 8^{i} \frac{n^3}{2^{3i}}\\ & = \sum_{i = 0}^{\log_2 n - 1} n^3\\ & = n^3 \log_2 n\\ \end{align*}$$

Now you can go ahead and use this in your substitution method and you should not have any issues.


Feel free to try the same method with a trickier example:

$$T(n) = \begin{cases} 12 & n = 3\\ 5T\left(\tfrac{n}{3}\right) + n^2 + n & n > 3\\ \end{cases}$$

$\endgroup$
0
$\begingroup$

You can prove a recurrence of the form $$aT(n/b) + f(n)$$ if the constraints for master theorem hold. A bad value for f(n) might invalidate that.

$\endgroup$
  • 1
    $\begingroup$ I don't think this quite answers the question. The Master Theorem will work, yes, but I believe they are asking specifically about how general the substitution method is for recurrences of this form. $\endgroup$ – ryan Apr 3 at 2:45
  • $\begingroup$ Yes, @ryan is correct — that doesn't answer my question. I know you can solve this easily with the master theorem and get that it is $\Theta(n^3\log n)$, that is in fact how I got my guess for the substitution. What I was asking was how one can show that $T(n)=8T(\frac{n}{2}) + n^3$ is asymptomatically lower bounded by $n^3 \log n$ using the substitution method. $\endgroup$ – Pabi Apr 3 at 12:22

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.