On 12/08/2015 04:25 PM, Andrei Alexandrescu wrote:
I'm working on the complexity algebra and of course trying to simplify
my life :o). One good simplification would be to get rid of
log(polynomial_sum) terms such as:
log(n + m)
log(n^^3 + n1^^2 + n2)
etc.
Do any of these occur in some important algorithms? I couldn't think of
any nor find any on the various complexity cheat sheets around.
Thanks,
Andrei
You don't need to support those terms in the internal representation,
because they don't add anything to the expressiveness of the notation:
O(log(n+m)) = O(log(n)+log(m)).
O(log(n^^3+n1^^2+n2)) = O(log(n)+log(n1)+log(n2)).
(I have already noted this in the other thread, in case you have missed it.)
