Solving recurrence T (n) = T (n / 3) + T (2n / 3) + n ^ 2?
I think this repetition works in & Theta; (n 2 ). To verify this, we show that T (n) = & Omega; (n 2 ) and that T (n) = O (n 2 ).
By showing that T (n) = & Omega; (n 2 ) is pretty simple - since T (n) has n 2 in it, it is definitely & Omega ;. (n 2 )
Let us now show that T (n) = O (n 2 ). We have that
T (n) = T (n / 3) + T (2n / 3) + n 2
Consider this other repetition:
S (n) = S (2n / 3) + S (2n / 3) + n 2 = 2S (2n / 3) + n 2
Since T (n) is increasing and T (n) & le; S (n), any upper bound for S (n) must also be an upper bound for T (n).
Using the main theorem on S (n), we get a = 2, b = 3/2, and c = 2. Since log b a = log 3/22 = 1.709511291 ... <c, the Main Theorem says that this will solve O (n 2 ). Since S (n) = O (n 2 ), it is also known that T (n) = O (n 2 ).
We have shown that T (n) = & Omega; (n 2 ) and that T (n) = O (n 2 ), therefore T (n) = & Theta; (n 2 ) if required.
Hope this helps!
(By the way, (5/9) log n = (2 log 5/9 ) log n = 2 log n log 5/9 = (2 log n ) log 5/9 = n log 5/9 . Makes this a little easier to reason about .)
source to share
This cannot be said about the execution time of T(n)
OR time complexity! It's just an estimate of the runtime in terms of the order of input (n).
One thing I would like to add: -
I haven't solved your recurrence, but remember that your derived relationship is correct and hence adding n = 1 to your recurrence will get
T(1)=T(1/3)+T(2/3)+1
So, either you will be given the values ββfor T(1/3)
and T(2/3)
in your question, or you must understand from the given problem operator as what it should be T(1)
for the Tower of Hanoi problem!
For repetition, the base register T(1)
, now by definition, has the following value:
T(1) = T(1/3) + T(2/3) + 1
Now, since T (n) denotes an executable function, then the execution time of any input that will not be processed is always 0
, this includes all members in the base case, so we have:
T(X < 1) = 0
T(1/3) = 0
T(2/3) = 0
T(1) = T(1/3) + T(2/3) + 1^2
T(1) = 0 + 0 + 1
T(1) = 1
Then we can substitute the value:
T(n) = n T(1) + [ (9/5)(n^2)( (5/9)^(log n) ) ]
T(n) = n + ( 9/5 n^2 (5/9)^(log n) )
T(n) = n^2 (9/5)^(1-log(n)) + n
We can approximate (9/5)^(1-log(n))
to 9/5
for an asymptotic upper bound because (9/5)^(1-log(n)) <= 9/5
:
T(n) ~ 9/5 n^2 + n
O(T(n)) = O(n^2)
source to share