What complexity have a log(sum) shape?

[Timon Gehr via Digitalmars-d]

On 12/09/2015 03:06 AM, Algo wrote:
> On Wednesday, 9 December 2015 at 01:40:12 UTC, Timon Gehr wrote:
>> On 12/09/2015 02:02 AM, H. S. Teoh via Digitalmars-d wrote:
>>> Big-O notation deals with asymptotic
>>> behaviour as the variables approach infinity, so behaviour at 'small'
>>> values of m and n are irrelevant.
>>
>> The problem is, however, that only m /or/ n could be small.
>
> Pretty sure as per property 1 (common, "weak" definition of
> multi-variate O class) no variable can be "small".

It certainly can be. Property 1 only talks about those values of the 
function where this is not the case though.

> For all n >= ntresh and for m >= mtresh the inequality must hold,
> and that's only the weakest property.

Exactly, it is a rather weak property. Other properties can (and should) 
also constrain functions in O(f(n,m)) on those values where one of the 
two variables is small.

You could have a function like:

void bar(int n)@Time(BigTheta("2^n"));

void foo(int n,int m){
     if(n<10) return bar(m);
     if(m<10) return bar(n);
     return 0;
}

If only property 1 is required, one can derive that foo runs in O(1), 
which is inadequate.