# Recurrent relation for algorithms with two stages

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$$.

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$$).