CiviCRM is distributed under a GNU AGPL 3 license; there are no legal limits as to the number of contacts or number of users you can have.
On the question of storage, it isn't easy to say definitively what a maximum number of contacts would be, or even how much disk space a certain number of contacts would require.
Contacts are only a small part of a CRM system. You're also recording event participation, contributions, memberships, mailings, and so on. The more numerous these data points, the faster your storage needs will multiply.
There can be huge variation in uploaded files like profile pictures, logos, or attached PDFs— these still count against any storage quota, even if they're not stored in the database.
Even considering the database alone, not every field of every record will be populated; turning off geocoding or stripping down greetings will make a difference.
Every site will have different custom fields, in number, type, and population.
Two identical databases can further differ based on the configuration of the system. For example, the number of characters you store in a database is different from the number of bytes of space it takes up. In a character set like Latin-1 (ISO-8859-1), all available characters can be stored in a single byte, but because UTF-8 includes a vastly larger range of characters, it might take up to 4 bytes (as of MySQL 5.6, MySQL will use up to three bytes) to do so. The differential will not be significant for Western European languages, but would be radically so if your database contained Chinese characters for example.
With MySQL, size limitations generally depend on the file system (which relates to the operating system). Since InnoDB tables can span multiple files, your db can be quite large indeed; however, the time and memory it takes to search through exceptionally large databases could render CiviCRM impractical, and this of course relates to how fast the hard disk is and how much memory is available, and how your MySQL is configured. There is a whole cottage industry around MySQL tuning, though many of the tools like MySQL Tuner wouldn't be usable in a shared hosting environment.
To illustrate, I have a CiviCRM 4.6.3 database with 2500 contacts in UTF-8 stored on an ext3 drive that is 202MB in size; there are various complex membership levels, monthly events, and frequent mailings maintained in CiviCRM. Another organization on the same server has almost 8800 records, also UTF-8, and 12 custom fields. Yet this database takes up only 13MB of space (!). That is because the vast majority of contacts are only a name and email address, and there are only a few dozen mailings stored in the system.