I'm working on the complexity algebra and of course trying to simplify my life :o). One good simplification would be to get rid of log(polynomial_sum) terms such as:

log(n + m)
log(n^^3 + n1^^2 + n2)

etc.

Do any of these occur in some important algorithms? I couldn't think of any nor find any on the various complexity cheat sheets around.


Thanks,

Andrei

On Tuesday, 8 December 2015 at 15:25:28 UTC, Andrei Alexandrescu wrote:
> I'm working on the complexity algebra and of course trying to simplify my life :o). One good simplification would be to get rid of log(polynomial_sum) terms such as:
>
> log(n + m)
> log(n^^3 + n1^^2 + n2)
>
> etc.
>
> Do any of these occur in some important algorithms? I couldn't think of any nor find any on the various complexity cheat sheets around.

It seems that for a complexity such as log(n + m) to make sense, it should be possible that both n is more than polynomially larger than m and that m is more than polynomially larger than s. Since obviously if for instance m < O(n^k), where k is a constant, then O(log(n + m)) = O(log n).

I guess that such situations are quite rare.

On Tuesday, 8 December 2015 at 16:25:50 UTC, tn wrote:
> ... and that m is more than polynomially larger than s. ...

Should of course be "larger than n".

On 12/08/2015 04:25 PM, Andrei Alexandrescu wrote:
> I'm working on the complexity algebra and of course trying to simplify
> my life :o). One good simplification would be to get rid of
> log(polynomial_sum) terms such as:
>
> log(n + m)
> log(n^^3 + n1^^2 + n2)
>
> etc.
>
> Do any of these occur in some important algorithms? I couldn't think of
> any nor find any on the various complexity cheat sheets around.
>
>
> Thanks,
>
> Andrei

You don't need to support those terms in the internal representation, because they don't add anything to the expressiveness of the notation:

O(log(n+m)) = O(log(n)+log(m)).

O(log(n^^3+n1^^2+n2)) = O(log(n)+log(n1)+log(n2)).

(I have already noted this in the other thread, in case you have missed it.)

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

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?

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?

Damn, I missed Timon's post, here is the link for anybody else: http://forum.dlang.org/thread/n3qq6e$2bis$1@digitalmars.com?page=10#post-n42ft2:2498u:241:40digitalmars.com

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.

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.

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)).