5
$\begingroup$

Prove or disprove the following statements:

  1. $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}$

  2. $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?

$\endgroup$
  • $\begingroup$ Just find a $c$ so that the inequality is fulfilled. This has been treated here and also here. $\endgroup$ – Raphael Oct 8 '12 at 10:35
  • $\begingroup$ And I know the first one is true,and second one is false. I just don't know why. $\endgroup$ – sam Oct 9 '12 at 6:23
  • $\begingroup$ Ok, the question is a bit more involved than if we have an $f$ given, and item 2. seems to be hard (are you sure it is wrong?). By the way, the assumption $n=2^k$ usually suggests that you should do something by hand, not with Master theorem. $\endgroup$ – Raphael Oct 9 '12 at 17:50
  • $\begingroup$ May I ask where you got this problem? It seems like possibly a good homework/exam question for a course I'm TAing and I'd like to know the source. $\endgroup$ – SamM Oct 9 '12 at 18:42
  • $\begingroup$ @Raphael here the $n=2^k$ may simply be because the author didn't want to deal with non-integer values when dividing by 2. (Note that there's no floor or ceiling in the recurrence). Of course that doesn't contradict what you said, but it's another possibility. $\endgroup$ – SamM Oct 9 '12 at 18:44
4
$\begingroup$

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. $$

$\endgroup$
  • $\begingroup$ Checking a piecewise defined function only at few positions and then talking about asymptotics doesn't feel right. I guess it just needs more words: $f \in \Omega(n^2)$ is clear, and you show $T(n) \notin O(n^2)$ without ever saying what complexity $T$ has. Nice. $\endgroup$ – Raphael Oct 9 '12 at 22:14
2
$\begingroup$

For 1., trouble is that you don't know $f$; it could be any one of the functions in $\Theta(n^2)$. Therefore, applying the master theorem directly is not (immediately) possible.

So let's unfold $\Theta$! Let $f \in \Theta(n^2)$ arbitrary. We know by definition of $\Theta$ that there are $d_1, d_2, n_1, n_2 \in \mathbb{N}$ such that

$\qquad \displaystyle d_1n^2 \leq f(n) \leq d_2n^2$,

for all $n \geq n_0 := \max(n_1,n_2)$. We will ignore all $n < n_0$ in the sequel; consider the respective values of $T$ constants.

We can easily show with the master theorem (case 3) that for

$\qquad\begin{align} T_1(n) &= 2T_1(n/2) + d_1n^2 \text{ and} \\ T_2(n) &= 2T_2(n/2) + d_2n^2 \end{align}$

both $T_1 \in \Theta(n^2)$ and $T_2 \in \Theta(n^2)$. Since we have (asymptotically) that $T_1(n) \leq T(n) \leq T_2(n)$, we also get that $T \in \Theta(n^2) = \Theta(f)$ by squeeze theorem.


As you see, we needed both upper and lower bound to perform the proof. We don't have that in the second case where $f \in \Omega(n^2)$. That suggests the statement may be false (but does not prove it).

Once we suspect, we can choose a counter-example; see Yuval's answer for one.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.