3
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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).
$\endgroup$
1
$\begingroup$

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}. $$

$\endgroup$
  • $\begingroup$ I have a doubt here : when we substitute n/2 in place of n calculating T(n/2) = 7 T(n/4) +(n/2)^2 , and after putting the value of T(n/2) in original equation it should be 7^2T(n/4) + (n/2)^2 + n^2 But in your proof above its: 7^2T(n/2^2)+7(n/2)^2+n^2. I want to know where is this extra 7 coming from (I mean 7(n/2)^2) $\endgroup$ – user16666 Apr 17 '14 at 22:41
  • $\begingroup$ The extra $7$ is there since $7T(n/2) = 7(7T(n/4) + (n/2)^2)$. $\endgroup$ – Yuval Filmus Apr 17 '14 at 22:42
0
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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})$

$\endgroup$
  • $\begingroup$ OP has got this already. He wants to determine the constant factor, so this isn't helpful at all. $\endgroup$ – gnasher729 May 19 '17 at 6:01

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.