I guess that depends on the size of each record, the type of database you use and what indexes you have set. But in general autocomplete uses a LIKE query which is definitely slower on a lot of records.
Really the only way you are going to know is to make sonme benchmarks. Implement a simple autocomplete and try it against a db with 1Mil rows.
-- Ezra Zygmuntowicz-- Lead Rails Evangelist
-- Engine Yard, Serious Rails Hosting
-- (866) 518-YARD (9273)