1
$\begingroup$

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<n<(k+1)b \end{cases} \end{equation*}

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

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Federico May 13 at 21:08

Your Answer

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

Browse other questions tagged or ask your own question.