recurrence relation with doubling stepping size I have the following recurrence
$$f(2n) = 2f(n)+n$$
By taking $f(1) = 1$ and then calculating a few values we can see that it grows in $$O(n \log n)$$
However is there a more algebraic way to come to that conclusion?
 A: As observed by @Liu Gang,
$$\frac{f(2n)}{2n}=\frac{f(n)}n+\frac12.$$
Defining $g(k):=\frac{f(2^k)}{2^k}$, we have 
$g(k+1)=g(k)+\frac12$, and $g(0)=1$.
Obviously, $g(k)=\frac k2+1$, and
$$f(n)=n(\frac{\lg n}2+1).$$
A: We set $n=\frac{m}{2}$,Then the recursive relation becomes: $f(m)=2f(\frac{m}{2})+\frac{m}{2}$

$$f(\frac{m}{2})=2f(\frac{m}{4})+\frac{m}{4}$$

We see that at each level the cost is $\frac{m}{2}$
The height is $k$,where $\frac{m}{2^{k+1}}=1 \Rightarrow m=2^{k+1} \Rightarrow \lg m=k+1 \Rightarrow k=\lg m-1$
So,the cost is $\frac{m}{2}+(\lg m-1) \frac{m}{2}=\frac{m}{2} \lg m$
Therefore, $f(m)=O(m \lg m) \Rightarrow f(2n)=O(n \lg n)$
A: clearly $f(0)=0$ and $$f(2)=2f(1)+1$$ $$f(2^2)=2f(2)+2=2^2f(1)+2+2$$  $$f(2^3)=2f(2^2)+2^2=2^3f(1)+2^2+2^2+2^2$$ $$f(2^4)=2f(2^3)+2^3=2^4f(1)+2^3+2^3+2^3+2^3$$  So, by mathematical induction we can show that $$f(2^n)=2^nf(1)+\dfrac{n}{2}2^n$$ I don't no, haw I can continuoue this to obtain a genaral solution for this functional equation. But I can assume that, Any solution would be take the form $$f(n)=nf(1)+\dfrac{n}{2}\log_2n.$$
