Re: [ontolog-forum] [SMW-devel] [News] Google, Microsoft, Facebook And O

[Simon Spero <sesuncedu@xxxxxxxxx>]

On Oct 11, 2012 5:24 PM, "Rich Cooper" <rich@xxxxxxxxxxxxxxxxxxxxxx> wrote:

> [ Of SQL ops like AND, OR, & NOT]  That time is very nearly linear rather than polynomial.  

I'm not quite sure what is meant here. Linear complexity O(n) is polynomial - O(n^1).

There are some  special cases where calculations can be performed in sub-linear time (e.g. some merges) , but   worst case complexity is still O(n).

Simon

_________________________________________________________________
Message Archives: http://ontolog.cim3.net/forum/ontolog-forum/  
Config Subscr: http://ontolog.cim3.net/mailman/listinfo/ontolog-forum/  
Unsubscribe: mailto:ontolog-forum-leave@xxxxxxxxxxxxxxxx
Shared Files: http://ontolog.cim3.net/file/
Community Wiki: http://ontolog.cim3.net/wiki/ 
To join: http://ontolog.cim3.net/cgi-bin/wiki.pl?WikiHomePage#nid1J    (01)