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 not my biggest concern to those kind of mass hosting configuration, but memory usage is. As each virtual host data structure will take certain amount of memory to store parsed configurations. Assume each one takes 1KB memory, you will be using 1-2GB memory just for vhost configurations. We can add a new class of virtual host which uses minimum memory for each virtual host.
However, there is one solution for LSWS (and Apache) right now, to use URL rewrite for mass hosting, only a domain name to document root mapping is required, it is fast (o(1) in lsws), memory efficient but lacking the flexibilities in configuration comparing to standalone virtual host.
To host 1-2 million virtual hosts on one server is not a easy job no matter what server software is used, I think. :-) LSWS has not added any special feature for that kind of applications yet, but we can if there are a lot of interest in that.