CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 2 of 2
  1. #1
    Join Date
    Mar 2010
    Posts
    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 !

  2. #2
    Join Date
    Oct 2006
    Posts
    616

    Re: Cant understand recurrence relation equation

    Quote Originally Posted by Hypernova View Post
    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 View Post
    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 View Post
    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
  •  





Click Here to Expand Forum to Full Width

Featured