This paper presents a novel method for applying approximate computing at the level of a complete application. The method decomposes the application into processing blocks which types define the classes of approximate computing techniques they may tolerate. By applying these approximation techniques to the most computationally intensive blocks, drastic energy reduction can be obtained at a limited cost in terms of Quality of Service. The algorithmic-level approximate computing method is applied to a software High Efficiency Video Coding (HEVC) video decoder. The method is shown to offer multiple trade-offs between the quality of the decoded video and the energy required for the decoding process. The algorithmic-level approximate computing method offers new possibilities in terms of application energy budgeting. Energy reductions of up to 40 percent are demonstrated for a limited degradation of the application Quality of Service.