Prove or disprove the following statement:
If $f(n)\in \Omega(n^2)$ and $T(n) = 2T(n/2) + f(n)$ then $T(n) \in O(f(n))$.

I think that the statement is false. Do you know any counterexamples?


Taking $n=2^k$, we have $$T(n)=2T\left(\frac{n}{2}\right)+f(n)=\\=2\left[2T\left(\frac{n}{2^2}\right) +f(n)\right]+f(n)=2^2T\left(\frac{n}{2^2}\right)+2f(n)+f(n)=\\=2^3T\left(\frac{n}{2^3}\right)+2^2f(n)+2f(n)+f(n)=\cdots=2^kT(1)+f(n)[2^{k-1}+\cdots+1]=\\=2^kT(1)+f(n)(2^k-1) = nT(1)+f(n)(n-1)$$ Now we have 2 cases: 1. $T,f$ are defined only for $2$s powers and 2. $T,f$ are defined on $\mathbb{N}$.

  1. Considering non negative functions, condition $T \in O(f)$ gives $$ f(n)(n-1) \leqslant T(n) \leqslant C f(n)$$ which is impossible for any below boundedness for $f$.

  2. If we demand $T$ defined on $\mathbb{N}$, then we come to necessity to define $T\left(\frac{n}{2}\right)$ which can be filled by OP.

| cite | improve this answer | |

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