This content has been marked as final.
Show 10 replies

1. Re: Solution to a recurrence relation
843853 Nov 10, 2009 1:19 PM (in response to 843853)I don't understand your notation
in relation toT(n) = T(2n/3) + T(1n/3) + n
I don't think this follows.T(2/3) = T(4n/9) + 2n/3 + n T(4/9) = T(8n/27) + 4n/9 + 2n/3 + n

2. Re: Solution to a recurrence relation
843853 Nov 11, 2009 12:55 AM (in response to 843853)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
Now what is the value of T(2n/3) ? substituting into the above equation, we getT(n) = T(2n/3) + n > equation 1
Substituting this value in equation (1) we getT(2n/3) = T(2(2n/3)/3) + 2n/3 = T(4n/9) + 2n/3
T(n) = T(4n/9) + 2n/3 + n

3. Re: Solution to a recurrence relation
843853 Nov 11, 2009 3:45 AM (in response to 843853)Now I'm even more lost. I thought your starting point was
but now you haveT(n) = T(2n/3) + T(1n/3) + n
so I don't understand where you are going and what you are asking.T(n) = T(2n/3) + n > equation 1
Are you looking for a closed form solution to 'equation 1' ? 
4. Re: Solution to a recurrence relation
843853 Nov 11, 2009 8:33 AM (in response to 843853)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 Nov 11, 2009 10:32 AM (in response to 843853)AUTOMATON wrote:
Is there a question here? All I see is a statement. What are you expecting from the forum members?
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. 
6. Re: Solution to a recurrence relation
843853 Nov 11, 2009 11:37 PM (in response to 843853)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 Nov 12, 2009 6:25 AM (in response to 843853)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 BigO 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 Dec 14, 2009 5:30 PM (in response to 843853)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 Dec 14, 2009 10:26 PM (in response to 843853)fridayda13 wrote:
Like what?
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. 
10. Re: Solution to a recurrence relation
843853 Dec 27, 2009 2:42 AM (in response to 843853)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.