Their document below says it is O(n), without specifying what n is there. If it is no of documents in the index then search can be extremely slow. This doesn't make any sense, or does it ?
https://oss.redislabs.com/redisearch/Commands.html#complexity_6
n is the number of the results in the result set, basically finding all the documents that have a specific term is O(1), then a scan on all those documents is needed to load the documents data from redis hashes and return them.