Performance Tuning
The search speed is influenced by various factors. The most important are:
Server Speed
Database Size
Number and quality of plugins installed (very high factor)
Shared hosting packages - Shared hosting providers usually have a paralell process execution cap (10-20 processes). While a shared server is fast, paralell connections or paralelly running processes can lead to extreme slowdowns. In this case I highly recommend Disabling the search when typing and the Autocomplete plugin functions.
VPS and Dedicated servers - The demo runs on a 10$/month Digital Ocean VPS with ubuntu LAMP stack installed. It's a 1GHZ single core, 1GB ram server - thus it's extremely cheap, and not that powerful. Yet the response times are extrelemly low. VPS is Highly recommended.
An everyday blog user or shop owner does not exceed 5-10000 posts/products, which is absolutely fine. A few thousand records should not affect the search speed greatly.
Larger databases (10000 records and more) may require a better database environment. On shared hosts, you might experience issues with such number of posts (regardless of the search plugin). In this case you might want to consider switching to a basic VPS. It provides much better performance, yet it's still cheap.
This is influences the search plugin the most. Usually a high number of (any number of low quality) plugins will decrease the overall WordPress performance - thus increasing the response time of any request, as well as ajax requests.
In my personal experience the wordpress site perfromacne strongly drops when:
Using 15+ active plugins with similar performances
..or using "large" plugins like WooCommerce, BuddyPress, BBPress, JetPack etc.. at the same time.
Running a performance profiler plugin might give you an insight on which plugins take the most resources during loading - but it might be different for ajax requests.
Using only the neccessary plugins makes your site faster and safer.
You can use the built in performance tracker to compare the search function speed to the ajax response speed.