-
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 !
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
|