Can someone concisely explain how we can find the closed form of a recurrence relation? I know the iterative process is generally the preferred method, but I'm having trouble deriving the steps and coming to a final solution. Here are two questions I've obtained from an old textbook. If possible, I'd greatly appreciate if the "where n is a power of 2" and "where e,f,g are positive integers and n is a multiple of f" effect the decisions we make whilst trying to conclude with a closed form.

$T(n) = T(\frac{n}{2}) + \log_2{n}, T(1) = 1$ and n is a power of 2

$T(n) = eT(n-f)+g$ and e,f,g > 0 and n is a multiple of f

Thank you!


For the first $T(n)$ is not defined unless $n$ is a power of $2.$ We are given $T(1)$ and can use the recurrence to find $T(2),$ but there is no way to find $T(3)$ unless we view the division as integer division and say $3/2=1.$ For recurrences like this, we usually care about asymptotic behavior, so we can just think about powers of $2.$

Similarly in the second, having $n$ a multiple of $f$ means the recurrence will bottom out at $0.$ Having $e,f,g \gt 0$ makes sure $T(n)$ doesn't go negative. The text is being careful to give well-stated problems.

Added: for the first, define $n=2^k$, so $k=\log_2 n$ and define $S(k)=T(2^k)=T(n)$. $S(k)$ is defined for all $k$. The recurrence becomes $S(k)=S(k-1)+k, S(0)=1$ By inspection we can see that $S(k)=1+\sum_{i=1}^k i=1+\frac 12 k(k+1)$ so $T(n)=1+\frac 12 \log_2 n (\log_2 n +1)$

For the second, let $m=\frac nf$ and define $P(m)=T(fm)=T(n)$. You didn't give a base case, so I will assume $T(0)=P(0)=0$. The recurrence becomes $P(m)=eP(m-1)+g$. If we just write out $P(3)=eP(2)+g=e(P(1)+g)+g=e(e(P(0)+g)+g)+g=e^2g+eg+g$ we can see that $P(m)=g\frac {e^m-1}{e-1}$ by summing the geometric series. You can make it more formal, but that is the answer. Now you would need to translate that back to the original $T(n)$

  • $\begingroup$ Thank you! Do you have any idea of a solution for these recurrences, or possible something online that can compute them for me (if the closed form by hand isn't readily accessible)? $\endgroup$ – Bob John Feb 6 '13 at 1:15
  • 1
    $\begingroup$ For the first let $k=\log_2 n$, for the second $m=n/f$ Both become fairly simple. $\endgroup$ – Ross Millikan Feb 6 '13 at 1:20
  • $\begingroup$ I'm sorry, I don't know how to proceed. Do you mind elaborating? I'm trying to use wolfram, but apparently I can't specify unknown values such as e,f, and g $\endgroup$ – Bob John Feb 6 '13 at 1:23
  • $\begingroup$ @BobJohn: See the added info. $\endgroup$ – Ross Millikan Feb 6 '13 at 14:49

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.