# Solving "runtime" of recurrence realtion with generating functions

• October 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:

$

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

$

where
$n \in \mathbb{N}$

If you let

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

then

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

so

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

Idealy I could write $A(t^2)$ in terms of $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 $A(t^2)$ in terms of $A(t)$. Has anyone ever come across this before?

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