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) &amp; = 2T(\frac{n}{2})+m \\
&amp; = 2T(\frac{n}{2})+n\\
&amp; = n+nlog_2n
\end{split}
\end{equation*}$$

Treating $m$ as a constant:
$$\begin{equation*}
\begin{split}
T(n) &amp;= 2T(\frac{n}{2})+m \\
&amp;= 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 &lt; 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$).