Approaches for dynamically allocating CPU cycles for use in processing a video stream. Video complexity information for two or more digital video streams actively being processed by one or more video encoders is determined at periodic intervals. Video complexity information describes the complexity of digital video carried by the digital video streams across a bounded number of consecutive digital frames which includes digital frames not yet processed by the one or more video encoders. A determination is made as to whether a number of CPU cycles allocated for processing a particular digital video stream should be adjusted based on the determined video complexity information. The number of CPU cycles allocated for processing the particular digital video stream may be dynamically adjusted by changing an amount of CPU cycles allocated to a virtual machine in which the stream is processed or by processing the stream in a different virtual machine.