From what I've read, around 80% of any appstore game downloads will be from organic traffic by people searching the app store. So It's better to invest in:
* Good description, SEO, tags, and search words.
* Nice app icon
* Nice Screenshots
* Possibly gameplay video
After that, it's good to get people talking about the game, so try sending out a nicely composed email to reviewers, youtubers, magazines, maybe local newspaper with a small press kit, and link to the game of course.