Return to Answer

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.

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.

Below proof is wrong; we need $c<1$ which can only work if $d_1 \leq 2d_2$ -- but there is no reason to believe that this should always be true.

The trouble is that you don't know $f$; it could be any one of the functions in $\Theta(n^2)$ resp. $\Omega(n^2)$.

So let's unfold the classes! In case one, whichever function $f \in \Theta(n^2)$ happens to be the "real" one, we know that there is a $d_1 \in \mathbb{N}$ such that

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

and also a $d_2 \in \mathbb{N}$ such that

$\qquad \displaystyle f(n) \geq d_2n^2$

for all $n \in \mathbb{N}$ (that are the $O$- resp. $\Omega$-part of $\Theta$). We have to show that there is some constant $c$ such that

$\qquad \displaystyle 2f(n/2) \leq cf(n)$.

With above inequalities, we get that $2f(n/2) \leq \frac{1}{2}d_1n^2$, and that $cd_2n^2 \leq cf(n)$. So, if we choose $c$ such that

$\qquad \displaystyle \frac{1}{2}d_1n^2 \leq cd_2n^2$,

  we have shown the necessary inequality. Note that $c=d_1$ already works ($d_1,d_2 > 0$).

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 just choose a counter-example. However, I have not been able to find one! Instead, some handwaving thinking suggests the following:

Conjecture
For $f\in \Omega(n^2)$, $f\left(\frac{n}{2}\right) < \frac{f(n)}{2}$.

This is quite plausible; I am not sure what wicked functions may do to the fraction, though. If this is the case, the factor $2$ is not able to compensate for the increase in the divisor $2$, and $f(n)$ dominates whole $T(n)$.

This line of reasoning is wrong, though. (It may be correct for "smooth" functions). See Yuval's answer for a counter-example.

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.

The trouble is that you don't know $f$; it could be any one of the functions in $\Theta(n^2)$ resp. $\Omega(n^2)$.

So let's unfold the classes! In case one, whichever function $f \in \Theta(n^2)$ happens to be the "real" one, we know that there is a $d_1 \in \mathbb{N}$ such that

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

and also a $d_2 \in \mathbb{N}$ such that

$\qquad \displaystyle f(n) \geq d_2n^2$

for all $n \in \mathbb{N}$ (that are the $O$- resp. $\Omega$-part of $\Theta$). We have to show that there is some constant $c$ such that

$\qquad \displaystyle 2f(n/2) \leq cf(n)$.

With above inequalities, we get that $2f(n/2) \leq \frac{1}{2}d_1n^2$, and that $cd_2n^2 \leq cf(n)$. So, if we choose $c$ such that

$\qquad \displaystyle \frac{1}{2}d_1n^2 \leq cd_2n^2$,

we have shown the necessary inequality. Note that $c=d_1$ already works ($d_1,d_2 > 0$).

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 just choose a counter-example. However, I have not been able to find one! Instead, some handwaving thinking suggests the following:

Conjecture
For $f\in \Omega(n^2)$, $f\left(\frac{n}{2}\right) < \frac{f(n)}{2}$.

This is quite plausible; I am not sure what wicked functions may do to the fraction, though. If this is the case, the factor $2$ is not able to compensate for the increase in the divisor $2$, and $f(n)$ dominates whole $T(n)$.

This line of reasoning is wrong, though. (It may be correct for "smooth" functions). See Yuval's answer for a counter-example.

Below proof is wrong; we need $c<1$ which can only work if $d_1 \leq 2d_2$ -- but there is no reason to believe that this should always be true.

The trouble is that you don't know $f$; it could be any one of the functions in $\Theta(n^2)$ resp. $\Omega(n^2)$.

So let's unfold the classes! In case one, whichever function $f \in \Theta(n^2)$ happens to be the "real" one, we know that there is a $d_1 \in \mathbb{N}$ such that

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

and also a $d_2 \in \mathbb{N}$ such that

$\qquad \displaystyle f(n) \geq d_2n^2$

for all $n \in \mathbb{N}$ (that are the $O$- resp. $\Omega$-part of $\Theta$). We have to show that there is some constant $c$ such that

$\qquad \displaystyle 2f(n/2) \leq cf(n)$.

With above inequalities, we get that $2f(n/2) \leq \frac{1}{2}d_1n^2$, and that $cd_2n^2 \leq cf(n)$. So, if we choose $c$ such that

$\qquad \displaystyle \frac{1}{2}d_1n^2 \leq cd_2n^2$,

we have shown the necessary inequality. Note that $c=d_1$ already works ($d_1,d_2 > 0$).

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 just choose a counter-example. However, I have not been able to find one! Instead, some handwaving thinking suggests the following:

Conjecture
For $f\in \Omega(n^2)$, $f\left(\frac{n}{2}\right) < \frac{f(n)}{2}$.

This is quite plausible; I am not sure what wicked functions may do to the fraction, though. If this is the case, the factor $2$ is not able to compensate for the increase in the divisor $2$, and $f(n)$ dominates whole $T(n)$.

This line of reasoning is wrong, though. (It may be correct for "smooth" functions). See Yuval's answer for a counter-example.