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? 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. 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 getT(n) = T(4n/9) + 2n/3 + n
T(n) = T(2n/3) + T(1n/3) + n
but now you haveT(n) = T(2n/3) + n ---------------> equation 1
so I don't understand where you are going and what you are asking.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.
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.