Complexity nomenclature

Andrei Alexandrescu via Digitalmars-d digitalmars-d at puremagic.com
Sat Dec 5 15:55:16 PST 2015


On 12/05/2015 04:52 PM, BLM768 wrote:
>
> Well, we could see how CAS libraries handle this kind of stuff (if there
> _is_ one which handles it)...

CAS = ?

> Really, though, with the more complex algorithms, you start running into
> the kinds of issues noted in the first reply to this article:
> http://www.perlmonks.org/?node_id=573138
>
> Besides, is anyone actually going to specify that they need an algorithm
> that is O(log(n) + m^2) or whatever? Or would a function just take _two_
> algorithms, assert that each is O(log(n)) and O(m^2), respectively, and
> then compose them itself? The complexities depend on the types of
> container anyway, so in general, you should get only multi-term big-O
> notation when you're using multiple containers (or Cartesian products of
> a container with itself or something like that). Can't we just make sure
> one container's insert() and the other container's sort() work within a
> certain complexity?

Well you'd need multiple terms if you want to say things like, 
"inserting a range into an array is O(array[].walkLength + 
r.walkLength)." When you insert a range in a binary search tree, the 
complexity would be O(log(array[].walkLength) * r.walkLength).

Part of the art here, I feel, is knowing when to stop going too crazy 
about this. At this point we have a nice, round system that's simple to 
understand and use. Making it more complex should come only with a 
corresponding growth in power.


Andrei



More information about the Digitalmars-d mailing list