By an accident, I run into this question from December 2011 asking, if 4 MB of executable size for mobile devices is too much for a simple application. Even though it is over 3,5 years after asking this question, the general rule remains. I found my answer to this question quite interesting and thus I'm sharing it in here.
You can answer this question, by simply browsing any mobile store in... games category!
You'll quickly learn, that application size of 50-150 MB is nothing for both mobile device and user, if only application is worth installing and using (is usable in case of your application or have a good gameplay and marketing, in case of game). If you convince user, that installing your app is worth, he or she will install it no matter, if it takes 4 MB or 40 MB.
Please note, that the fact, that I'm answering in middle of 2015 (3,5 years after asking your question) and possible hardware expansion / growth during this period of time, has nothing to do with this. Even in time of asking this question (end of 2011) apps like Facebook or Google+ had around 50 MB of size and everyone was installing them, because they were Facebook or Google+, i.e. because people wanted to have them, not even thinking about application size or device performance.
You should also notice another thing. It is quite obvious, that people, who are installing apps from mobile stores doesn't even care for the requirements particular application has (and thus so many dumb user's devices are infected by bad software). If they don't even check requirements, how can we think, that they'll ever matter about app size?
I can imagine (purely theoretical numbers, no source), that if only 25% of users spares 2-3 seconds to check app requirements (or think, if it can do any harm to the device) then number of users, who are actually checking application size (or care about this at all) is around 5-10%, so close to statistical error.
If only your application is interesting to end user, he or she most likely won't take much care about your application size. And thus you shouldn't care much about it as well.