What complexity have a log(sum) shape?
Charles via Digitalmars-d
digitalmars-d at puremagic.com
Tue Dec 8 13:30:09 PST 2015
On Tuesday, 8 December 2015 at 20:56:28 UTC, cym13 wrote:
> On Tuesday, 8 December 2015 at 17:33:49 UTC, Andrei
> Alexandrescu wrote:
>> On 12/08/2015 12:12 PM, Timon Gehr wrote:
>>> O(log(n+m)) = O(log(n)+log(m)).
>>
>> Noice. Yes I did miss it. Thx!! -- Andrei
>
> Surely I'm missing something obvious but why is it true exactly?
Im confident it isn't. I think the rule he was thinking of was
O(log(ab)) = O(log(a)+log(b)), which is just a basic property of
logarithms. It's pretty easy to get to a contradiction between
those two rules.
More information about the Digitalmars-d
mailing list