Computing symbolic complexity bounds of loops can prove program’s termination. Based on the solving techniques of recurrence equations and optimization problems, this paper presents a practical approach for computing complexity bounds of loops called P*-solvable loops. Two algorithms are given for loops with assignments only and loops with conditional branches respectively. Compared with some other works, this approach can attain more complexity bounds of loops. The experimental results demonstrate the practicality of this approach.