An online system receives video data items from users and encodes the video data items using various codecs. To account for different computational resources used for encoding using different codecs, the online system ranks combinations of video data items by ratios of encoding video data items with different codecs to computational costs of encoding different video data items with different codecs. The benefit of encoding a video data item with a codec is based on a compression efficiency of the codec and a predicted aggregate amount of the video data item displayed to various users of the online system. Encoding video data items with codecs based on the determined ratios allows the online system to optimize a duration of video data having at least a threshold video quality to users.