Discussion on answer by nore: Fastest algorithm to take the product of all subsets

Actually, it turns out my proof is incorrect. I'd be interested if anyone has a correct proof, it looks like this question is actually quite classic (there are a few other copies of it in other stackexchange sites, and it seems to be asked quite often at job interviews), but I have not been able to find any proof of a lower bound on the number of operations needed.