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)$$

The simplified form (without ceiling or floor operators) is kept because in algorithmic analysis, we are only interested in the asymptotic complexity, where the floor and ceiling functions are mostly irrelevant. The same holds for the Master theorem. A more powerful generalization known as the Akra-Bazzi method also gives asymptotic bounds.

There is a very good treatment of solving various types of recurrences using various methods in these lecture notes by Jeff Erickson. There is a reference question on the sister site cs.se: link

As for the terminology, I am not sure but I would simply call it a divide-and-conquer recurrence.

-
It should be mandatory to include this explanation whenever someone asks us to solve one of these recurrences. –  GEdgar Feb 12 '13 at 14:08