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 !