What complexity have a log(sum) shape?

[Timon Gehr via Digitalmars-d]

On 12/08/2015 10:35 PM, Charles wrote:
> 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.

The context is asymptotic runtime bounds. The special cases for small 
values of continuous logarithms can just be defined away. They have no 
relevance for asymptotic runtime analysis (even though defining big-O 
adequately for multiple variables is more tricky than for a single 
variable).