I wouldn't suggest a VPS in place of shared hosting, for a number of reasons.
Let's assume your budget is £30 per month - from bytemark.co.uk this gives you
- 1000MB RAM
- 1 CPU Core
- 20GB storage
The downsides of using a VPS being
- You need to manage your own server. That means you have to optimise the server, monitor the server, fix any issues with the server - have you got that level of experience?
- Your I/O is shared. Anyone else's activity using the common HDDs will bottleneck anything your Magento store needs to do
- You are limited to 1GB RAM, to put this into perspective ...
Each PHP thread (visitor) needs an average 30MB RAM and its corresponding MySQL connection will need just a bit more. So that is 80MB per visitor. Your base OS needs about 140MB RAM to run. MySQL base wants as much as possible, but as a minimum, it will need 300MB.
So you are using 440MB, leaving you support for 7 active visitors - which is fortunate, because 1 2.5GHz core can push through a maximum of 7 requests per second (for Magento).
Conversely, you could pick a Magento host that already optimises its shared servers, uses external DB servers, and usually has a powerful machine that you can burst resources on, to a factor of around 8 of what your VPS offers.
There are a few Magento hosting comparison sites out there that will help you make this decision.