1
$\begingroup$

The substitution method for recurrence solving wants you to come up with a guess function $g(n)$ which has the property $g(n) \in O(f(n))$. The goal is to show that your recurrence $T(n) \in O(f(n))$. In order to do that, you claim $T(n) \leq g(n)$ and substitute accordingly until you have that exact term.

Example: $$T(n) = 2T(n/2) + n$$ $$T(n) \leq cn^2 - dn$$

Substitution: $$T(n/2) \leq c(n/2)^2 - (d/2)n = (c/4)n^2 - (d/2)n$$

So: $$T(n) = 2T(n/2) + n$$ $$T(n) \leq 2[(c/4)n^2 - (d/2)n]+n$$ $$T(n) \leq (c/2)n^2 - dn+n$$

Multiply with 2, property is not violated. $$T(n) \leq cn^2 - 2dn + 2n$$

If we assume $d \geq 2$ $$T(n) \leq cn^2 - dn$$

Our function $g(n) = cn^2 - dn$ and we tried to show that $T(n) = O(n^2)$ because $g(n) \in O(n^2)$.

Assume we failed to do the proof this well and we got something like: $$T(n) \leq (ac + b)n^2 - (xd+y)n$$

Observe that $a, b, c, d, x, y$ are all constants.

Would it be possible to claim $(ac + b) = c_2$ and $(xd+y) = d_2$?

Is this new expression $c_2n^2 - d_2n$ another function $g_2(n) \in O(n^2)$?

Would this indirectly still prove that $T(n)\in O(n^2)$?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

No, you can't.

As an example, consider the recurrence $T(n) = 4T\left(\frac{n}2\right) + n^2$.

If you assume $T(n) \leqslant cn^2 - dn$, using substitution method, you will get to:

$$T(n) \leqslant 4\times c\frac{n^2}4 - 4\times d\frac{n}2 + n^2 = (c+1)n^2-2dn$$

Even if $(c+1)n^2-2dn\in \mathcal{O}(n^2)$, you cannot conclude that $T(n) \in \mathcal{O}(n^2)$.

Indeed, you can prove by induction that for all $k$: $$T(n) = 4^kT\left(\frac{n}{2^k}\right)+\sum\limits_{i=0}^{k-1}n^2$$ If $n$ is a power of $2$, then for $k = \log_2 n$, $T(n) = 4^kT(1) + n^2\log_2 n = \Omega(n^2\log n)$.

Improve this answer
$\endgroup$
6
  • $\begingroup$ While n^2 log n is the best solution, you could conclude that the factor n^2 is a little bit too small, and c * n^2.01 will lead to a solution once n is large. Of course then you would figure thst n^2.001 can be made to work, and n^2.0001 and so on. $\endgroup$
    – gnasher729
    Commented Feb 17 at 20:20
  • $\begingroup$ @gnasher729 How is that relevant to the question? $\endgroup$
    – Nathaniel
    Commented Feb 18 at 0:42
  • $\begingroup$ @Nathaniel, so the "proof by induction" you made. Isn't that the iterative method? We called it "repeated backward substitution." In your case, we first determine what $T(n/2)$ is and then plug it into $T(n) = 4T(n/2) + n^2$. Do that repeatedly and usually after the third one, you see a pattern which then yields to the one you got with $k$. But to respond to your answer. So even if we know that $T(n) \leq (c+1)n^2 - 2dn$, we cannot conclude that $T(n) \in O(n^2)$? Big-O refers to the upper bound and we already know that a "thing greater than $T(n)$" is bounded by $O(n^2)$. $\endgroup$
    – Yuirike
    Commented Feb 18 at 10:47
  • $\begingroup$ @Yuirike The problem is with the hypothesis: we assumed that $T(n)\leqslant cn^2-dn$, which is wrong, as I have proved that $T(n) \in \Omega(n^2\log n)$. $\endgroup$
    – Nathaniel
    Commented Feb 18 at 12:58
  • $\begingroup$ @Nathaniel So ultimately, if I fail to make a "right guess", it is more efficient to use other methods, presumably repeated backward substitution or recursion trees. Generally, the substitution method is kind of based on that as well, the "guess" is something you kind of derive after seeing a pattern. $\endgroup$
    – Yuirike
    Commented Feb 19 at 6:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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