What complexity have a log(sum) shape?

cym13 via Digitalmars-d digitalmars-d at puremagic.com
Tue Dec 8 13:33:58 PST 2015


On Tuesday, 8 December 2015 at 21:30:09 UTC, Charles wrote:
> 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.

No, his demonstration stands. This isn't about log algebra, it's 
about asymptotic notation. I missed the fact that O(a+b) = 
O(max(a, b)).


More information about the Digitalmars-d mailing list