What complexity have a log(sum) shape?

[Charles via Digitalmars-d]

On Tuesday, 8 December 2015 at 21:18:01 UTC, Timon Gehr wrote:
> On 12/08/2015 09:56 PM, 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?
>
> n+m ≤ 2·max(n,m). (1)
> max(n,m) ≤ n+m.   (2)
>
> Hence,
>
> log(n+m) ≤ log(max(n,m)) + log(2)       by (1)
>          = max(log(n),log(m)) + log(2)  by monotonicity
>          ≤ log(n) + log(m) + log(2)     by (2),
>
> log(n)+log(m) ≤ 2·max(log(n),log(m))    by (1)
>               = 2·log(max(n,m))         by monotonicity
>               ≤ 2·log(n+m)              by " and (2).
>
> Similar arguments work for any monotone increasing function 
> that does not grow too fast.

This seems reasonable, but you have undefined behavior of 
logarithms if n or m is zero.