Depends on the price of the VPS as well. You need a nice amount of CPU share and hard disk IO for encoding, so you will need to pay well for it. On a VPS, you are sharing hard disk IO, so it affects other users too and it is not worth for a provider to provide a VPS for one client while it affects many others.