CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

# Thread: Cant understand recurrence relation equation

1. Junior Member
Join Date
Mar 2010
Posts
1

## Cant understand recurrence relation equation

Hi !

I am having trouble understanding the meaning of equations of the type-

T(n)=aT(n/b) + f(n)

I have just started recurrence relations, so my questions may be a little stupid, and probably not very clear, but it'll be great if you could try to help me out...

1. What is T(n) ?
My prof says its the problem....but that doesnt make sense, what exactly is T(n), like is it the running time or complexity or something else OF the problem ? Knowing this will also make it clear what T(n/b) is...

2. What is f(n) ?
Is it the complexity or time required to merge the sub-solutions of the sub-problems...? (or something else completely ?)

3. The sense of the whole equation ?
Why are aT(n/b) and f(n) added together and why is their sum is equal to T(n)? They seem to be completely different things.....this is a purely mathematical equation in the end, and not some notation right ?

2. ## Re: Cant understand recurrence relation equation

Originally Posted by Hypernova
1. What is T(n) ?
My prof says its the problem....but that doesnt make sense, what exactly is T(n), like is it the running time or complexity or something else OF the problem ? Knowing this will also make it clear what T(n/b) is...
T(n) is simply a function. It is a recursive function because it references itself on both sides of the equation. T(n) could represent different things, but in computer-science, it is often used to represent an algorithm "run-time", or number of performed steps.

Originally Posted by Hypernova
2. What is f(n) ?
Is it the complexity or time required to merge the sub-solutions of the sub-problems...? (or something else completely ?)
Surprisingly, f(n) is also a function. Usually, in computer-science, inside the context of a T(n) equation, it represents a function simpler to compute, like the number of steps performed by an algorithm on each recursive call.

Originally Posted by Hypernova
3. The sense of the whole equation ?
Why are aT(n/b) and f(n) added together and why is their sum is equal to T(n)? They seem to be completely different things.....this is a purely mathematical equation in the end, and not some notation right ?
Right ! this is a pure mathematical notation. Forget about computer science when you look at it !!! (but not when you try to analyze it).

I can give a simple example:
Code:
```unsigned int factorial(unsigned int n)
{
if (n <= 1) {
return 1;
} else {
return n * factorial(n-1);
}
}```
What is the number of steps done by the recursive function above ?
We can say that:
1. If n <= 1 then the number of steps, T(n), would be 2 (check the 1st 'if' condition, then return 1 - a total of 2 steps).
2. If n > 1 then we can try to represent the number of steps with a recursive formula. What would this formula be ?
Let's count the number of steps:
On each recursive call, there if one check of the 'if' condition, that's one step.
Then, assuming n > 1, there is a multiplication of n with the result of another recursive call. The multiplication is another step, so there are a total of 2 steps. The recursive call is factorial(n-1), so it's cost in number of performed steps is T(n-1).

To sum it all up, the recursion number of steps formula would be:
Code:
```T(1) = 2;
T(n) = T(n-1) + 2```
(2 for the 2 steps performed, and T(n-1) for the recursive call).
If you put this into the template T(n) = aT(n/b) + f(n), then
a = 1, b = n/(n-1), and f(n) = 2.

Note: For asymptotic analysis you could simplify the formula by counting any number of consecutive steps which are bounded by a constant , as a single step (since they are O(1)).

I hope this made things clearer.

Regards,
Zachm

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•