Recurrent relation for algorithms with two stages
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$).