On our demo site we are running on 64MB, that is the WordPress minimum requirement, that should be more than enough.
The actual search plugin peak memory usage in our case is on average is below 0.25MB, based on ~40000 logged queries recently. So 1MB in theory is enough for the plugin, but it’s more complicated than that.
The actual full ajax request memory usage depends on your whole system setup and the overhead, which is beyond the search itself. It’s similar when a page is opened, WordPress needs to load it’s core, plugins etc.. – and the more plugins there are, the more overhead it generates, as the plugins may execute additional code etc.. You need to adjust that according to your exact setup.
I generally recommend minimizing plugins amounts as much as possible, and making sure to use plugins which are high quality and does not load unneccessarily and generate less overhead. That unfortunately does not correlate with plugin popularity, I have seen very popular plugins loading all of their resources for no reason everywhere, slowing down the whole environment.
Also make sure to check the performance optimization guide to get the best out of the search.