Is the bitstream for the decoder a lot more complex?

From what I recall (and it has been a few years), usually the standard mostly specifies what the 'end product' will look like and the encoders basically have to figure out a way to get there. The decoding was usually pretty expensive and had a lot of quality options and was constantly trying to detect things like global motion compensation etc, while the decoder basically just decoded the same old bitstream without a lot of change in complexity for the same profile level.