What complexity have a log(sum) shape?

[Timon Gehr via Digitalmars-d]

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.