This discussion is archived
10 Replies Latest reply: Dec 27, 2009 12:42 AM by 843853 RSS

Solution to a recurrence relation

843853 Newbie
Currently Being Moderated
Hey,

Don't know if this is appropriate here, as the question is rather math oriented.

I have a recurrence relation of the form:-
T(n) = T(2n/3) + T(1n/3) + n
The solution, using the tree method comes out to be nlogn. However, I am not able to solve it using iterative method. I would appreciate if someone verifies the solution.
Since T(2n/3) would form the biggest branch, it is the dominant term. We can thus write T(n) = T(2n/3) + n, as T(1/3n) will have little effect in the long run.

T(2/3) = T(4n/9) + 2n/3 + n
T(4/9) = T(8n/27) + 4n/9 + 2n/3 + n

= T({2/3 ^ k}n) + SIGMA[i=0 to k-1] (2/3)^i * n

n= (3/2)^k

k=logn (with base base 3/2 from now on)
putting k= logn we get
T(1) + SIGMA[i=0 to logn-1] (2/3)^i n
= O(1) + n * SIGMA[i=0 to logn-1] (2/3)^i
< O(1) + n * SIGMA[i=0 to infinity] (2/3)^i
Since this is a geometric series of decreasing terms, the summation evaluates to a constant, and the whole thing just leaves an "n" behind. The solution thus becomes O(n), which is incorrect. Can someone help with this?
  • 1. Re: Solution to a recurrence relation
    843853 Newbie
    Currently Being Moderated
    I don't understand your notation
    T(n) = T(2n/3) + T(1n/3) + n
    in relation to
    T(2/3) = T(4n/9) + 2n/3 + n
    T(4/9) = T(8n/27) + 4n/9 + 2n/3 + n
    I don't think this follows.
  • 2. Re: Solution to a recurrence relation
    843853 Newbie
    Currently Being Moderated
    Basically I am trying to expand the recurrence relation by continuously substituting the previous value to get the next value.

    There is actually an error in the notations. T(2/3), T(4/9) should actually be T(2n/3), T(4n/9). Sorry for the typo :)


    So if to start with you have
    T(n) = T(2n/3)  +  n  ---------------> equation 1
    Now what is the value of T(2n/3) ? substituting into the above equation, we get
    T(2n/3) = T(2(2n/3)/3) + 2n/3
               = T(4n/9) + 2n/3
    Substituting this value in equation (1) we get
    T(n) = T(4n/9) + 2n/3 + n
  • 3. Re: Solution to a recurrence relation
    843853 Newbie
    Currently Being Moderated
    Now I'm even more lost. I thought your starting point was
    T(n) = T(2n/3) + T(1n/3) + n
    but now you have
    T(n) = T(2n/3)  +  n  ---------------> equation 1
    so I don't understand where you are going and what you are asking.

    Are you looking for a closed form solution to 'equation 1' ?
  • 4. Re: Solution to a recurrence relation
    843853 Newbie
    Currently Being Moderated
    Yes, the original equation was

    T(n) = T(2n/3) + T(n/3) + n

    However, For the asymptotic running time for this relation, the term T(n/3) is ignored by me. Look at it this way. Draw a recursion tree for this and you will see that the branch depicted by T(2n/3) is longer, so this is the dominant term in deciding the running time. T(n/3) can be safely ignored for ease of calculation. T(n/3) reaches the leaves of the tree (i.e. T(1) ) MUCH more quickly and terminates.
  • 5. Re: Solution to a recurrence relation
    843853 Newbie
    Currently Being Moderated
    AUTOMATON wrote:
    Yes, the original equation was

    T(n) = T(2n/3) + T(n/3) + n

    However, For the asymptotic running time for this relation, the term T(n/3) is ignored by me. Look at it this way. Draw a recursion tree for this and you will see that the branch depicted by T(2n/3) is longer, so this is the dominant term in deciding the running time. T(n/3) can be safely ignored for ease of calculation. T(n/3) reaches the leaves of the tree (i.e. T(1) ) MUCH more quickly and terminates.
    Is there a question here? All I see is a statement. What are you expecting from the forum members?
  • 6. Re: Solution to a recurrence relation
    843853 Newbie
    Currently Being Moderated
    Previous reply is a statement because it is a clarification. You asked for it, I provided it. The question in my first post, last paragraph still stands. I don't know if my approach is correct. The recursion tree method yeilds a complexity of O( n log n), iteration method results in O( n ) which is incorrect. I want to solve it via iteration, but the answer is wrong. Where am I going wrong?? Conceptually, things "seem" to be correct, apparently they are not.
  • 7. Re: Solution to a recurrence relation
    843853 Newbie
    Currently Being Moderated
    Sorry but I think you are making some questionable assumptions and it is not clear to me what you want from the forum members. The Big-O for your recurrence relation seems to be one that is featured in the exercises in the book "Introduction to Algorithms" by Corman et al. Maybe this book or one of the million and 1 solutions given by Google can help.

    Bye
  • 8. Re: Solution to a recurrence relation
    843853 Newbie
    Currently Being Moderated
    I don't understand why you treat him like this.
    I am looking also fr the correct solution for this same problem, and I can't figure it out.
    If anyone here knows how to solve the problem T(n) = T(n/3) + (T2n/3) + n, at least two people will appreciate it very much.
  • 9. Re: Solution to a recurrence relation
    843853 Newbie
    Currently Being Moderated
    fridayda13 wrote:
    I don't understand why you treat him like this.
    Like what?
    I am looking also fr the correct solution for this same problem, and I can't figure it out.
    If anyone here knows how to solve the problem T(n) = T(n/3) + (T2n/3) + n, at least two people will appreciate it very much.
  • 10. Re: Solution to a recurrence relation
    843853 Newbie
    Currently Being Moderated
    Your mistake was when you decided that you could ignore the T(1n/3) term. You were correct that it does not dominate the depth of the recursion but you were incorrect when you assumed that it could be ignored entirely.

    -- Iteratively --

    T(n) = [T(n/3)] + [T(2n/3)] + n

    then you expand both of the terms in brackets to get

    T(n) = [T(n/9) + T(2n/9) + n/3] + [T(2n/9) + T(4n/9) + 2n/3] + n

    now notice that on the first pass you did n operation and on the second pass you did n/3 + 2n/3 operations which is another n operations.

    On each pass you do n operations.

    In your analysis you decided that you did n*(some geometric series) which is n*(some constant) and hence is O(n) but in reality you did
    n + n + n + n ... k times and k is NOT a constant. k is lg(n)

    So iteratively you get O(n*lg(n)) just as expected from the tree analysis.

    Think about the difference between a divide and conquer algorithm where you split a group of size n in half and must process both halves versus one where you split it in half and get to ignore one of the halves. The lg(n) term tells you how many passes you must do and if you must do n operations on each pass (as you must when you process both halves) you will be at n*lg(n) but if you get to throw half away each time you are doing n*(1 + 1/2 + 1/4 + ...) = n*2 amount of work which is O(n) not n*lg(n).

    You can not just toss away half (or in this case a third) of the calculation and say, "that term doesn't matter." That is where you ran into trouble.