-
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 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 ?
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 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
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|