# A Recurrence relations of the form: $T(n) = aT(\frac{n}{b}) + f(n)$

1. Is there a name / terminology used for describing the above type of recurrence relation?
2. Is there a general method for finding a closed form for these types of recurrences?
3. When does a closed form exist?

According to this post the above relation would be considered linear.

These relations occur allot in algorithms and the master theorem is used to find upper bounds on their running time.

-
What kind of number is $b$? – 1015 Feb 12 '13 at 12:32
$a,b\in \mathbb{N}$ – Robert S. Barnes Feb 12 '13 at 12:36
What about $n/b$? $T(\cdot)$ is defined for naturals or reals? – leonbloy Feb 12 '13 at 12:47
The more general form of the Master Theorem gives upper and lower bounds ($\Theta$), not just upper bounds. – Rick Decker Feb 12 '13 at 13:44
"the above relation would be considered linear" ... yes, we would say it is linear, inhomogeneous. Unless $f(n)=0$, in that case it is linear, homogeneous. – GEdgar Feb 12 '13 at 14:10

In algorithms, these recurrences are almost always defined only for natural $n$. So, in the current form, they will only be defined if $n$ is a power of $b$.
If you want to be pedantic, the correct way to represent such recurrences is to use the ceiling or the floor function as appropriate. Something like: $$T(n) = aT\left(\left\lfloor \frac{n}{b}\right\rfloor\right) + f(n)$$