1

Define $f:\mathbb Z\rightarrow\mathbb Z$ recursively as follows: $f(1)=1$ and $f(n)=2f(⌊\frac{n}2⌋)+n$ for $n\geq2$. Prove that $f(n)=O(nlogn)$ for any integer $n\geq1$.

I've tried to prove $f(n)\leq cnlog(n)$ with mathematical induction but I failed right at the beginning as I can't even figure out how to prove the base case. $f(1)=1$ but for R.H.S. it is $0$.

Also for the induction part I know that $f(2)=4$,$f(4)=12$,$f(8)=32,...$ and for R.H.S. it will be $2log2, 8log2, 24log2$,... respectively. And I observed that for $n\geq4$ when R.H.S is the $n$ term, $\frac{cnlog(n)}{c\frac{n}2log(\frac{n}2)}=\frac{f(\frac{n}2)}{f(\frac{n}4)}$ in L.H.S. but I don't know how to present it properly.

I have weak mathematical background and when it comes across new topic for me I find it difficult. Can someone gives me hints on how to prove this question? Or am I wrong right from the beginning?

Foolishking
  • 11

1 Answers1

1

Assuming $n=2^k$, let's make few steps: $$f(n)=2f\left( \frac{n}{2} \right)+n=2\left[2f\left( \frac{n}{2^2} \right)+\frac{n}{2} \right]+n=\\ =2^2f\left( \frac{n}{2^2} \right)+2n=2^3f\left( \frac{n}{2^3} \right)+3n=\cdots=\\ =2^kf\left( \frac{n}{2^k} \right)+kn$$ Now using $k=\log_{2}n$, we obtain $$f(n)=nf(1)+n\log_{2}n \in O(n\log n)$$

zkutch
  • 13,410