recurrence relation with doubling stepping size

Question

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?

Answer 1

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)$

Answer 2

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.$$

Answer 3

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).$$