Yeah I feel like you can't have true instant search without autocomplete. Lots of people don't realize that the reason Google's instant search is effective is that they can tell what you are going to type before you finish typing it. Autocomplete would be huge.

You guys can probably do a pretty effective version right now but I imagine data about what people are searching for allows you to create a better autocomplete feature. And that data only comes with time.