Techniques for selecting a picture of a video program for display in accordance with a selected trick play mode of a DVR are described herein. Sometimes, when desired playback speed is faster than normal, a DVR is forced to select some pictures to play and some pictures to skip. Ideally, in order to preserve “smooth” viewing quality, the next picture to be displayed should be temporally close to the currently displayed picture. Since some pictures can take longer to decode than others, accounting for picture decoding costs helps ensure that the best picture can be selected for decoding given playback speed requirements. According to one embodiment of the invention, for each picture of a plurality of pictures in a video data stream, a DVR determines a decoding cost for that picture. Based on the determined costs, the DVR selects a particular picture. The DVR outputs the selected picture for display.