# Solving "runtime" of recurrence realtion with generating functions

• Oct 6th 2009, 11:29 AM
gmatt
Solving "runtime" of recurrence realtion with generating functions
Hi,

In computer science often the "runtime" of an algorithm can be described with a recurrence relation, here is an example:

$\displaystyle T(n) = \left\{ \begin{array}{lr} c & n = 1 \\ T( \lfloor n/2 \rfloor ) + n & n > 1 \end{array} \right.$
where
$\displaystyle n \in \mathbb{N}$

If you let

$\displaystyle A(t) = \sum _ {n = 0} ^ \infty T(n) t^n$

then

$\displaystyle \sum _{n=0} ^ \infty T(\lfloor n/2 \rfloor) t^n= (1 + t)A(t^2)$

so

$\displaystyle A(t) - (1+t)A(t^2) = \sum _ {n=0} ^\infty n t ^n = \frac{t}{(1-t)^2}$

Idealy I could write $\displaystyle A(t^2)$ in terms of $\displaystyle A(t)$ somehow then use partial fractions and find the appropriate taylor series to solve this. The problem is I don't know how to proceed, how to write $\displaystyle A(t^2)$ in terms of $\displaystyle A(t)$. Has anyone ever come across this before?

This is purely for interest sake, no rush, any hints greatly appreciated.