To prove the recurrence by substitution method $T(n) = 7T(n/2) + n^2$

Question

I have done the proof until the point when $T(n) \leq cn^{\log7}$.

But when it comes to finding the value of constant $c$, I am getting stuck.

The given recurrence relation is $T(n) = 7T(n/2) + n^2$.

Since we already calculated the solution above which is $cn^{\log 7}$.

Inductive step:

Now we have to prove that $T(n) \leq c n^{\log7}$ where $c$ is a positive constant. If we consider that the solution holds good for $n/2$ then we can prove that it works for $n$ also: $$T(n/2) \leq c(n/2)^{\log7}.$$ Substituting these values in the recurrence relation:

$$ \begin{align*} T(n) &\leq 7c/(2)^{\log7} \times (n)^{\log7} + n^2 \\ &\leq cn^{\log7}, \text{ since $7/(2)^{\log7}$ is constant so can be ignored and $cn^{\log7} \gg n^2$ for large $n$} \\ &\leq cn^{\log7} \text{ assuming $c$ is a constant $\geq 1$.} \end{align*} $$

Finally to find constant $c$,

$$(7/(2)^{\log7}) \times cn^{\log7} + n^2 \leq cn^{\log7}. $$

I am not able to find appropriate $c$ for which the condition holds true.

Answer 1

You're headed in the right direction, but you need an intermediate step. Permit me to simplify things a bit by defining $\lg n = \log_2n$.

A Dead End

Your substitution method, where you want to establish that $T(n) \le cn^{\lg7}$ inductively, using the assumption $T(n/2)\le c(n/2)^{\lg 7}$ runs into problems, as you've already seen. Here's what happens: $$\begin{align} T(n) &= 7T\left(\frac{n}{2}\right)+n^2&\text{by definition}\\ &\le 7\left[c\left(\frac{n}{2}\right)^{lg7}\right]+n^2&\text{by the inductive assumption}\\ &=7\left[c\frac{n^{\lg7}}{7}\right]+n^2&\text{since $2^{lg 7}=7$}\\ &=c\,n^{\lg7}+n^2 \end{align}$$ and you'll obviously never be able to find a $c$ for which $c\,n^{\lg7}+n^2\le c\,n^{\lg 7}$.

A Way Out

The problem is that the $n^2$ term is messing you up. If it weren't there, then substitution would work. Suppose, for instance, that we had the simpler recurrence $S(n)=7\,S(n/2)$. Now life would be easy, since then the proof above would go through nicely. Assume that $S(n)\le c\,n^{\lg7}$. Then we'd have $$\begin{align} S(n) &= 7S\left(\frac{n}{2}\right)&\text{by definition}\\ &\le 7\left[c\left(\frac{n}{2}\right)^{lg7}\right]&\text{by the inductive assumption}\\ &=7\left[c\frac{n^{\lg7}}{7}\right]\\ &=c\,n^{\lg7}&\text{as required} \end{align}$$ and if you do this again and again, driving $n$ down to $1$, you'll find that you can choose any $c\ge S(1)$.

Transforming the Dead End Into the Way Out

Let's make the $n^2$ term go away. Let $S(n) = T(n)+k\,n^2$. Then from $$ T(n)=7\,T(n/2)+n^2 $$ we have, substituting and simplifying, $$\begin{align} S(n)-k\,n^2&=7\,[S(n/2)-k(n/2)^2]+n^2&\text{and so}\\ S(n) &= 7\,S(n/2)+n^2(k-7k/4+1) \end{align}$$ and it's not hard to see that $k=4/3$ will make the $n^2$ term vanish, giving the $S$ recurrence we just solved above. Putting these together we have $$ T(n)+\frac{4}{3}n^2=S(n)\le c\,n^{\lg7} $$ and so $$ T(n)\le c\,n^{\lg7}-\frac{4}{3}n^2<c\,n^{\lg7} $$

Lessons Learned

Truth to tell, I'd attack this problem by iterative expansion, namely the way Yuval did it in his answer, but these "substitution method" questions come up often enough that I thought this cautionary tale was warranted. The lessons to be learned here are

• The method of substitution often doesn't work when applied to a recurrence relation.
• It always applies to recurrences of the form $S(n)=p\,S(n/q)$ as long as $q\ne0$
• A useful tool to have in your kit is knowing that sometimes you can transform a complicated recurrence into a simple one by suitable addition (or, sometimes, multiplication).

Answer 2

Suppose $n$ is a power of $2$, say $n = 2^k$, and suppose $T(1) = 1$. Then $$ \begin{align*} T(n) &= 7T(n/2) + n^2 \\ &= 7^2T(n/2^2) + 7(n/2)^2 + n^2 \\ &= 7^3T(n/2^3) + 7^2(n/2^2)^2 + 7(n/2)^2 + n^2 \\ &=\cdots \\ &= 7^k + 7^{k-1} 4^1 + \cdots + 7^1 4^{k-1} + 4^k \\ &= 7^k \left(1 + \frac{4}{7} + \cdots + \left(\frac{4}{7}\right)^k\right) \\ &= 7^k \frac{1-(4/7)^{k+1}}{1-4/7} \\ &= (1 - (4/7)^{k+1}) \frac{7}{3} 7^k \\ &= \left(1 - \tfrac{4}{7} n^{\log_2 (4/7)} \right) \frac{7}{3} n^{\log_2 7}. \end{align*} $$ Therefore for $n = 2^k$, $$ T(n) \sim \frac{7}{3} n^{\log_2 7}. $$

Answer 3

When you calculate $T(2^k)$, you first start with T(1), which gets multiplied by 7 k times, giving $T(1)·7^k$.

But when you calculated T(2), you added a term $n^2 = 2^2$, which gets multiplied by 7 (k-1) times, giving $2^2·7^(k-1) = 7^k·(4/7)$.

When you calculated T(4), you added a term $n^2 = 4^2$, which gets multiplied by 7 (k-2) times, giving $4^2·7^(k-2) = 7^k·(4/7)^2$.

The same happens for the other intermediate terms, so your result is $7^k$, multiplied by (T (1) + (4/7) + (4/7)^2 + (4/7)^3 + (4/7)^4 ...), which is a geometric series with a sum of T (1) + 4/3. So c = T (1) + 4/3.

(A bit of care is needed: T (1) + 4/3 is the limit, but you asked for an upper bound. In this case since the values add up, the limit is the upper bound, but that wouldn't work for $T(n) = 7·T(n/2) - n^2$. )

You can use this approach for many similar recurrences. And it will show a problem instantly for the recurrence $T(n) = 7·T(n/2) + n^3$.

Answer 4

Use the master theorem:

https://en.wikipedia.org/wiki/Master_theorem

by case 1, if $f(n)= O(n^{2<{log_{2}7}})$ then $T(n)= O(n^{log_{2}7})$