
March 30th, 2010, 07:46 AM
#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 subsolutions of the subproblems...? (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 ?
I appreciate your help !

March 31st, 2010, 03:39 AM
#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 computerscience, it is often used to represent an algorithm "runtime", or number of performed steps.
Originally Posted by Hypernova
2. What is f(n) ?
Is it the complexity or time required to merge the subsolutions of the subproblems...? (or something else completely ?)
Surprisingly, f(n) is also a function. Usually, in computerscience, 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(n1);
}
}
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(n1), so it's cost in number of performed steps is T(n1).
To sum it all up, the recursion number of steps formula would be:
Code:
T(1) = 2;
T(n) = T(n1) + 2
(2 for the 2 steps performed, and T(n1) for the recursive call).
If you put this into the template T(n) = aT(n/b) + f(n), then
a = 1, b = n/(n1), 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

Forum Rules

Click Here to Expand Forum to Full Width
