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