It depends on how the mapping is configured, for explicit domain name matching, hash map is used in LSWS, so it should be O(1), for wild card domain name (with * or ?) matching, regex is used and each pattern has to be processed one by one, so it is O(n).
Scalability of virtual mapping is...