Your best approach is probably to set up a unit test with the maximum number of expected features and run it multiple times in a few different browsers to get an accurate idea of how long exactly it will take. You can base it on an OpenLayers unit test (see here for more details on setting one up) or an example such as this one.
A few factors will affect this:
- the number of features in the map at anyone time, although you'll probably notice slow loading / panning times before you even get to querying the features
- the type of geometry you are querying. If it is a point OpenLayers simply checks if the other point has the same coordinates. If it is a polygon then it loops through each vertex to see if it falls in the other polygon.
There are a few other options before you start looping through geometries. You could get the bounds of each geometry, and seeing which of these intersect to filter out many of the features, before comparing the remaining geometries.
I've also found the distanceTo function to be useful, though this could be slower than intersects.