With recent advances in computing and communication technologies, ubiquitous access to high quality multimedia content such as high definition video using smart phones, Net books, or tablets is a fact of our daily life. However, power is still a major concern for any mobile device, and requires optimization of power consumption using a power model for each multimedia application, such as a video decoder. In this paper, a generic decoding complexity model for the motion compensation (MC) process, which constitutes up to 25% of the computational complexity and hence power consumption of an H.264/AVC decoder, has been proposed. For the model to remain independent from a specific implementation or platform, it has been developed by analysing the MC algorithm as described in the standard. Simulation results indicate that the proposed model estimates MC complexity with an average accuracy of 95.63%, for a wide range of test sequences using both JM and x.264 software implementations of H.264/AVC. For a dedicated hardware implementation of the MC module the modeling accuracy is around 89.61%, according to our simulation results. It should be noted that in addition to power consumption control, the proposed model can be used for designing a receiver-aware H.264/AVC encoder, where the complexity constraints of the receiver side are taken into account during compression.