Find a function f(n) such that T(n) is $\Theta(n \cdot log(n)) $

Question

Find a function f(n) such that $ T(n)=16 \cdot T(\frac{n}{4}) + f(n) = \Theta(n \cdot log(n)) $

Also, another section of the question is where $T(n) = \Theta(n^{2})$

I've tried using the master method in reverse, but have failed to accomplish anything.

Any ideas?

EDIT! My apologies! I have just discovered that some of the questions were meant to be unsolvable, the matter is understood then. Thank you all for your guidelines!

Answer 1

This will not be possible. Notice that under the (very natural) assumption that $f\geq 0$, then you get $$ T(n) \geq 16 T\!\left(\frac{n}{4}\right) $$ so that $T(n) \geq T^\prime(n)$ where $T^\prime$ is defined by the same initial conditions as $T$ and satisfies $$ T^\prime(n) = 16 T^\prime\!\left(\frac{n}{4}\right) $$ Not, solving this last recurrence (e.g., via the Master theorem, although in this case it is overkill) results in $T^\prime(n) = \Theta(n^2)$. Therefore, we get $T(n) = \Omega(n^2)$, ruling out the possibility that $T(n) = \Theta(n\log n)$.

---

Note that getting $T(n) = \Theta(n^2\log n)$, however, is possible, so it may have been a typo.