2
$\begingroup$

So I have read the posts on this site involving recurrence relations, however this problem is a little different, because of the constant a involved with the recursive portion. I'm trying to solve this recurrence relation by expanding it out and here is what I have so far:

enter image description here

I'm not sure where to go from here and how to find the asmpytotic bounds.

$\endgroup$
4
  • $\begingroup$ Welcome to Computer Science! 1. Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. 2. en.wikipedia.org/wiki/Geometric_series $\endgroup$
    – D.W.
    Commented Apr 23, 2016 at 4:20
  • $\begingroup$ Please specify the initial condition of the recurrence relation. What is the value of T(1) exactly. From what I can make out it is equal to c. Is this what it is? $\endgroup$
    – Prateek
    Commented Apr 23, 2016 at 14:45
  • 1
    $\begingroup$ There are $n/2$ terms and not $\log_2 n$ terms in the expansion. And why can't you do a sum on a geometric series? But your approach is correct. $\endgroup$ Commented Apr 23, 2016 at 15:29
  • $\begingroup$ Hi. So there are n/2 terms? And yes sorry T(1) here is equal to c. I was thinking a sum of geometric series, but im not sure how to go about doing that with the constant a. Would the aspytotic bound here just be a constant? $\endgroup$
    – Mike
    Commented Apr 24, 2016 at 7:01

2 Answers 2

2
$\begingroup$

The first four lines of your argument were correct; all you missed was the proper generalization. In general, we see that $$ T(n) = c+c\alpha+c\alpha^2+\dotsb+c\alpha^{j-1}+\alpha^j T(n-2j) $$ Now we want to drive $T(n-2j)$ down to a value we know, namely $T(1)=c$. To do this we'll need $n-2j=1$ and so we set $j=(n-1)/2$, giving us $$\begin{align} T(n) &= c+c\alpha+c\alpha^2+\dotsb+c\alpha^{j-1}+\alpha^j T(n-2j)\\ &= c+c\alpha+c\alpha^2+\dotsb+c\alpha^{(n-1)/2-1}+\alpha^{(n-1)/2} c\\ &= c(1+\alpha+\alpha^2+\dotsb+\alpha^{(n-1)/2}) \end{align}$$ and this is just a geometric series, so I'll leave the last steps to you.

$\endgroup$
1
$\begingroup$

The trick here is to solve a modified recurrence in which there is no constant. Let $S(n) = T(n) - C/(1-\alpha)$. Then $$ S(n) = T(n) - C/(1-\alpha) = C + \alpha T(n-2) - C/(1-\alpha) = \\ C + \alpha (S(n-2) + C/(1-\alpha)) - C/(1-\alpha) = \alpha S(n-2). $$ (I found the constant $C/(1-\alpha)$ by solving linear equations.)

The solution to $S(n)$ with initial conditions $S(0),S(1)$ is easily found to be $$ S(2n) = \alpha^n S(0), \qquad S(2n+1) = \alpha^n S(1). $$ It follows that $$ T(2n) = \alpha^n (T(0) - C/(1-\alpha)) + C/(1-\alpha), \\ T(2n+1) = \alpha^n (T(1) - C/(1-\alpha)) + C/(1-\alpha). $$

$\endgroup$

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.