A function f(n) satisfies the recurrence f(n)=4f(n/2)+n for real numbers. Give an upper bound for f(n)?

Question

A function f(n) satisfies the recurrence f(n)=4*f(n/2)+n for real numbers. Give an upper bound for f(n)?

I get somewhere T(n) = Θ(n^2), is that correct?

Answer 1

Given $f(n)=4f(n/2)+n$, we can make the following chain of substitutions:

If $g(x):=f(2^{x+1})$, then $f(2^{x+1})=4f(2^x)+2^{x+1}$ tells us that $g(x+1)=4g(x)+2^{x+1}$.

If $h(x)=\frac{g(x)}{4^x}$, then (after some algebra), we obtain $h(x+1)=h(x)+(\frac{1}{2})^{x+1}$.

We then recognise this as a convergent infinite geometric series, and thus $h(x)=\Theta(1)$, $g(x)=\Theta(4^x), f(x)=\Theta(x^2)$