Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
  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.

share|improve this question
    
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
show 1 more comment

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.