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$
  • $\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. Apr 23 '16 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 Apr 23 '16 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$ – Shreesh Apr 23 '16 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 Apr 24 '16 at 7:01
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, privacy policy and cookie policy

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