3
$\begingroup$

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?

2 Answers 2

1

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

  • 0
    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)$.2012-06-14
0

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

  • 0
    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.2012-06-14