Recurrent relation for algorithms with two stages

Question

I am trying to do the recurrence relation for my algorithm, but it has two variables $T(n,m)$. For sufficiently small $n$, $m$ is practically the same as $n$, but $m$ cannot grow beyond some constant $k$. So once $n$ grows beyond $k$, $m$ turns to constant $k$. So it has two different stages.

I have done the relation in both cases: when $m$ is another variable, and when $m$ is a constant, but how do I put them together?

Using $a=2, b=2$ as an example: this recurrence relation with $m$ as a variable like $n$: $$T(1)=1$$ $$\begin{equation*} \begin{split} T(n) & = 2T(\frac{n}{2})+m \\ & = 2T(\frac{n}{2})+n\\ & = n+nlog_2n \end{split} \end{equation*}$$

Treating $m$ as a constant: $$\begin{equation*} \begin{split} T(n) &= 2T(\frac{n}{2})+m \\ &= n+mn-m \end{split}\end{equation*}$$

Please feel free to check my math. Now how do I represent this as one recurrence relation? $m$ cannot grow beyond constant $k$.

Answer 1

Just solve both cases separately. I.e., consider cases for $m < k$ and $m = k$ separately. The solution for the first one (i.e., $T(n, k - 1)$) gives the starting point for the second recurrence (i.e., $T'(n) = T(n, k)$, presumably for $n \ge k$).