Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In a syllabus of mine, they try to find a closed form of the following recurrence relation

$$\begin{align*} T(2k) &\leq 3T(k) + ck & k \geq 1\\ T(1) &= 1 \end{align*}$$

The method I usually use to find the closed form of a recurrence is expand it a few times and try to find a pattern. Then I verify that pattern using induction.

In my syllabus they only show the verification part, by using $T(2^l) \leq c(3^l - 2^l)$ as hypothesis, where $c$ is chosen such $T(2)\leq c$ and $l \geq 1$.

So, I tried expanding the recurrence relation to see where I could find that pattern, but I don't get anything close to it.

For example:

$$\begin{align*}T(2^l) &\leq 3(3T(2^{l-2})+c2^{l-2})+c2^{l-1}\\ &= 3^2T(2^{l-2})+3c2^{l-2}+c2^{l-1}\\ &= 3^2T(2^{l-2})+5c2^{l-2}\\ &\leq 3^2(3T(2^{l-3})+c2^{l-3})+5c2^{l-2}\\ &= 3^3T(2^{l-3})+3^2c2^{l-3}+10c2^{l-3} \end{align*}$$

So, my guess is, since they multiply $3^l$ by $c$, you can subtract $c2^l$ and still remain bigger than $T(2^l)$. But, while expanding, I doubt I would have come up with that.

So my question: is there perhaps a method that I can use to find this hypothesis by expanding, and without to many `magic' manipulations to get to that hypothesis?

share|improve this question

2 Answers 2

up vote 1 down vote accepted

Hint: Consider $S(k)=T(2^k)+c\cdot2^k$. Show that $S(k+1)\leqslant 3S(k)$. Compute $S(0)$. Deduce that $S(k)\leqslant 3^k(1+c)$ for every $k\geqslant0$ and, finally, that $T(2^k)\leqslant 3^k+c\cdot(3^k-2^k)$ for every $k\geqslant0$.

share|improve this answer
    
Don't we $3^k$ to much now? –  sxd Jun 14 '12 at 18:04
    
This is due to your use of the same symbol $c$ for two different quantities, namely the factor in the recursion and the upper bound of $T(2)$. Once you will have made up your mind about this, you will just have to adapt the hints in my answer, possibly starting from $T(2)$ and/or $S(1)$ instead of $T(1)$ and/or $S(0)$. –  Did Jun 14 '12 at 18:25

You can use the "Master Theorem" for solving recurrences. This is a general method of solving recurrences of the form $$ T(n) = a T(n/b) + f(n) $$ In this case, we have $$ T(n) = 3 T(n/2) + c/2 n $$

Here $f(n)$ satisfies $f(n) = O(n^{\log_b a - \epsilon})$, hence we have $$ T(n) = \Theta(n^{\log_b a}) = \Theta(n^{1.58}) $$

share|improve this answer
    
I'm not looking to solve this recurrence that way. I'm just search for the way that they came up with that hypothesis. Thanks though. –  sxd Jun 14 '12 at 18:22

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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