# how to prove recursive function f(x) is in O(n)?

Let f(n) be defined recursively as follows: \begin{align}f(0) &= 0 \\ f(n) &= f\left(\left \lfloor \frac{n}{3} \right \rfloor\right) + 3f\left(\left \lfloor \frac{n}{5} \right \rfloor\right) +n,\quad\forall n \ge 1 \end{align} Show that $$f(n)\in\mathcal O(n)$$.

I find some similar question that $$f(n) = 2f\left(\left \lfloor \frac{n}{2} \right \rfloor\right) + 1$$, but I don't know how to deal with the $$\left \lfloor \frac{n}{3} \right \rfloor$$ and $$n$$. can anyone give me some hint?

• sorry,you are right,I have made it correct – Krwlng Jul 16 '20 at 0:57

Let us prove that $$f(n)\le 30n$$. It is true for $$n=0$$. Suppose it is true for every $$m< n$$. Then $$f(n)=f(\lfloor\frac{n}{3}\rfloor) + 3f(\lfloor\frac{n}{5}\rfloor ) )+n\le 30\lfloor\frac{n}{3}\rfloor+90\lfloor\frac{n}{5}\rfloor+n\le 10n+18n+n<30n$$. Q.E.D.

• thank you very much! I am trying to understand your prove process. It means that if for all m<n ,f(m)<=30m,and since floor(n/3) and floor(n/5) are both less than n,so floor(n/3)<10n and floor(n/5) < 18n,right? And I also want to ask that do I have to claim that f(n) is non-decreasing? – Krwlng Jul 16 '20 at 2:29
• No, since $\lfloor n/3\rfloor <n$, $f( \lfloor n/3\rfloor} <30*\lfloor n/3\rfloor$. I do not assume that $f$ is non-decreasing. – Mark Sapir Jul 16 '20 at 2:32
• I understand,thank you professor. – Krwlng Jul 16 '20 at 2:39
• The qiestion still looks unanswered. If you are satisfird with an answer, you shoild accept it. – Mark Sapir Jul 16 '20 at 11:35
• sure,thanks for the reminder. – Krwlng Jul 16 '20 at 12:16

Since $$n$$ is positive and the initial condition is non-negative, it is easy to show that $$f$$ is non-decreasing. So,

$$f(\lceil n/3\rceil) \leq f(n)$$

• Sorry, I submitted by mistake. I'm trying to delete this answer – harwiltz Jul 16 '20 at 1:25