# A problem about master theorem and recursion [duplicate]

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.