In Part 1 of this paper the concept of a bound for the output frequency response magnitude characteristics of nonlinear systems was proposed, and general calculation and analysis procedures were developed. In this, Part 2 of the paper, a new recursive algorithm for the computation of the gain bounds for the generalized frequency response functions of the polynomial nonlinear autoregressive model with exogenous input is proposed, and effective procedures for the practical computation of the new bound are developed. Simulated examples are included to verify the effectiveness of the proposed procedures.