patternMinor
Problems showing the constraint of master theorem case three holds
Viewed 0 times
casethreeholdstheshowingmastertheoremconstraintproblems
Problem
Prove or disprove the following statements:
-
$T\left( n \right) = 2T\left( {\frac{n}{2}} \right) + f\left( n \right),f\left( n \right) = \theta \left( {{n^2}} \right) $ then $ {\rm{ }}T\left( n \right) = \theta \left( {f\left( n \right)} \right) $ for all $ {\rm{ n = }}{{\rm{2}}^k}$
-
$T\left( n \right) = 2T\left( {\frac{n}{2}} \right) + f\left( n \right),f\left( n \right) = \Omega \left( {{n^2}} \right) $ then $ {\rm{ }}T\left( n \right) = O\left( {f\left( n \right)} \right)$ for all $ {\rm{ n = }}{{\rm{2}}^k}$
I think I should use the third case of the master theorem to check these equations.
But I have not been able to check this constraint for these inequations:
$\qquad af\left( {\frac{n}{b}} \right) \le cf\left( n \right)$
How do I do that?
-
$T\left( n \right) = 2T\left( {\frac{n}{2}} \right) + f\left( n \right),f\left( n \right) = \theta \left( {{n^2}} \right) $ then $ {\rm{ }}T\left( n \right) = \theta \left( {f\left( n \right)} \right) $ for all $ {\rm{ n = }}{{\rm{2}}^k}$
-
$T\left( n \right) = 2T\left( {\frac{n}{2}} \right) + f\left( n \right),f\left( n \right) = \Omega \left( {{n^2}} \right) $ then $ {\rm{ }}T\left( n \right) = O\left( {f\left( n \right)} \right)$ for all $ {\rm{ n = }}{{\rm{2}}^k}$
I think I should use the third case of the master theorem to check these equations.
But I have not been able to check this constraint for these inequations:
$\qquad af\left( {\frac{n}{b}} \right) \le cf\left( n \right)$
How do I do that?
Solution
The following shows that the second statement is false.
Define $f$ as follows:
$$ f(n) = \begin{cases} 4n^3 & n \text{ is a power of }4, \\ n^2 & \text{otherwise}. \end{cases} $$
Let $n = 2^{2k+1}$. Then $f(n) = n^2$ while
$$ T(n) \geq 2T(n/2) \geq 2f(n/2) = n^3. $$
Define $f$ as follows:
$$ f(n) = \begin{cases} 4n^3 & n \text{ is a power of }4, \\ n^2 & \text{otherwise}. \end{cases} $$
Let $n = 2^{2k+1}$. Then $f(n) = n^2$ while
$$ T(n) \geq 2T(n/2) \geq 2f(n/2) = n^3. $$
Context
StackExchange Computer Science Q#4945, answer score: 4
Revisions (0)
No revisions yet.