SEO Budget? -- Rough estimate?

One of my small clients wants to rank his website (iOS + Android app in the lifestyle and travel industries). I'm interested in basic SEO stuff, but I'm not a professional (not yet) so I can't do it myself. He may want to hire a pro.

He wants to know what a SEO (backlinks, etc.) budget could look like. He needs something safe, something efficient and something that won't require hours of maintenance every week.

Now, I totally understand that every project is different and that there are many variables influencing the amount of work necessary to achieve this. But he needs a general idea of the budget to see if he can even consider it. Is it $50, $500, $5000? Per year? What can be done with a modest and honest budget?

I trust people on this forum, and I'm sure you guys can give me honest advice.
Don't send me private messages with offers, I won't reply. I want the conversation to be public.

Outsource or DIY SEO?

$500 - $1,000 a month is a good start for general.

Here I found another post where most commenters agree that $300 is a good starting budget http://www.blackhatworld.com/blackh...t-search-engine-optimization-please-help.html

$1k per month for anything worthwhile but it depends on where you want to compete. $500 a month could get you new customers for "Buttfucknowhere NJ carpet cleaner" but nothing less than $30k/mo if you want a shot at building a six figure per month revenue.

$300 don't really get you anything safe if you don't do it yourself. If you want managed SEO service that is both efficient AND safe-ish, you'll be looking more like a $1000-$3000/month.