do I have to pay for a private server to get magento to work?

Question

I'm new to magento and am confused about installing it (community ed.). My web provider (123 reg) are saying I need to buy a virtual private server because the memory requirement needs to be on a server of least 256MB. Do i have to pay for vps hosting to get it to work, or is there another way? i thought magento was potentially free

I probably haven't explained the problem very clearly, but here is what 123 reg support said:

"The Magento application is a heavy eShop to maintain on a shared hosting plan where the memory output is 128Mb, if you check the system requirements Magento needs to be hosted on a server with at least 256 Mb: http://magento.com/resources/system-requirements

This being given if you ought to upgrade from a shared plan to a VPS it would be possible to host the eShop there, please see our offers page if you are interested to purchase a VPS, this will also offers database management where you can import a SQL file with no size limitations: https://www.123-reg.co.uk/vps-hosting/

Even if was to run on the current plan you have it is not recommended as it will constantly go offline due to insufficient resources."