Cant understand recurrence relation equation

Quote:

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.

Quote:

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.

Quote:

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