Summary: In this paper, we propose an analytic solution for a special class of nonlinear recurrence relations. We describe these recurrence relations for the complexity function of recursive algorithms, developed by the decomposition method, with the union of solutions obtained having linear complexity. We obtain analytic solutions for two subclasses that arise in the theoretical analysis of this class of recurrence relations. The results can be used to obtain explicit complexity functions for recursive algorithms that decompose the problem being solved with the union of results having linear complexity.