# Under what assumptions is this recursively defined function non-decreasing?

Let

• $$\mathbb{N}^{+} = \mathbb{N}-\{0\}$$
• $$a_{1}$$, $$a_{2} \in [0,+\infty)$$ be such that $$a = a_{1}+a_{2} > 0$$
• $$b \in (1,+\infty)$$
• $$f\colon\ \mathbb{N}^{+} \to (0,+\infty)$$
• $$c_{1}$$, $$\dots$$, $$c_{\lceil b-1 \rceil} \in (0,+\infty)$$ be such that $$c_{1} \leq \dots \leq c_{\lceil b-1 \rceil}$$

and consider the function $$T \colon\ \mathbb{N}^{+} \to (0,+\infty)$$ defined as follow:

$$\begin{equation*} T(n) = \begin{cases} c_{1} & n=1 \\ \vdots \\ c_{\lceil b-1 \rceil} & n=\lceil b-1 \rceil \\ a_{1} T(\lfloor \frac{n}{b} \rfloor) + a_{2} T(\lceil \frac{n}{b} \rceil) + f(n) & n \geq b \end{cases} \end{equation*}$$

To give a little bit of context, this function comes from the time complexity analysis of divide-and-conquer algorithms.

Under what assumptions (on $$f$$, which I think should be the only relevant bit) can I be sure that $$T$$ is non-decreasing? Please provide at least some justification.

I think expressing $$T$$ in the following way might be of some help:

$$\begin{equation*} T(n) = \begin{cases} c_{1} & n=1 \\ \vdots \\ c_{\lceil b-1 \rceil} & n= \lceil b-1 \rceil \\ a T(k) + f(n) & n=kb \\ a_{1} T(k) + a_{2} T(k+1) + f(n) & kb

where $$k$$ ranges all over $$\mathbb{N}^{+}$$.

• After some thought, I came to the conclusion that asking $a \geq 1$ and $f$ to be non-decreasing is sufficient and that these hypotheses should also be minimal. I also realized that because of how I formulated the problem I should have really taken $b \in [2,+\infty)$, since $\lceil n/b \rceil < n$ for all $n \geq b$ if and only if $b \geq 2$. – Federico May 13 at 21:08