Dinko Tenev wrote: > Speculation: the time for > building-up a smart structure to speed-up enumeration, together with > the time for enumerating the set using that structure, should sum up to > roughly Theta( n*|S^n| ), even with a really smart algorithm.
OK, maybe not. This might be the worst case, looking at S^n - W only, but it's not quite clear what "worst case" means in the context of concrete implementations. Surely, one can clog the program with zillions of wildcards to test, so we can produce an arbitrarily "bad" case :) -- but such a case is obviously of little or no practical importance. It appears that, to make any sensible statements about performance in the relevant cases, we have to take into account the size of the pattern set used to specify W as well. > [...] here's another speculation: > such structure would likely take up Theta( |S^n| ) space in memory, in > the worst case. ...and similarly for "worst case" here. Cheers, Dinko -- http://mail.python.org/mailman/listinfo/python-list
