When using the MPEG-4 standard, the several video objects composing a scene may vary in size along time and may be encoded at different temporal rates using different macroblock (MB) coding types. To limit the decoding complexity of the corresponding bitstreams, it is then necessary to put some limits on the variability of the number and type of MB/s as well as on the bitrate and on the picture memory required to store the decoded data. This paper evaluates the decoding complexity of the several MB types used in MPEG-4 video coding, by using statistics of the MB decoding times obtained with an optimized MPEG4 video decoder. Based on these statistics, this paper proposes a set of relative complexity weights for the relevant MB complexity classes, which can be used to improve on the MPEG4 Video Complexity Verifier (VCV) model [1].