Also depends on the quality of the work prices can range from £250 - £20000 depending on factors here there and everywhere. best thing to do is find someone else who has had it done and ask for there opinion of the company.
Price will also vary dependent upon experience of who's doing the work and how good they are. The real problem you're up against is how to tell if you're going to get your money's worth and not have your site banned or trashed.
If you don't know SEO that well then I strongly urge you to learn as much as you can about what NOT to do as well as what should be done.
When you begin the process of interviewing SEO firms/people for the job, be prepared to ask lots of questions. And then be prepared to listen to and understand the answers. The potential contractor should be able to explain what they intend to do such that you'll understand it.
As far as cost goes, if the site has never been optimized and your market is competitive - expect to pay good money.
If you're looking for someone to not only optimize the site but also to help you manage your ad campaigns and help you understand how to realize your ROI - expect to pay even more.
Consider it an education and be prepared to learn fast. All in all, they're selling knowledge as well as their services and there isn't a textbook out there that can teach you what a good SEO/SEM person has learned on their own.