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?

  • $\begingroup$ sorry,you are right,I have made it correct $\endgroup$ – 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.

  • $\begingroup$ 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? $\endgroup$ – Krwlng Jul 16 '20 at 2:29
  • $\begingroup$ 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. $\endgroup$ – Mark Sapir Jul 16 '20 at 2:32
  • $\begingroup$ I understand,thank you professor. $\endgroup$ – Krwlng Jul 16 '20 at 2:39
  • $\begingroup$ The qiestion still looks unanswered. If you are satisfird with an answer, you shoild accept it. $\endgroup$ – Mark Sapir Jul 16 '20 at 11:35
  • $\begingroup$ sure,thanks for the reminder. $\endgroup$ – 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) $$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.