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

["Rich Cooper" <rich@xxxxxxxxxxxxxxxxxxxxxx>]

Dear Simon,

 

Yes, O(n^1) is polynomial in a sense.  What I was trying to point out is simply that the main performance issue in SQL databases is far more often disk speed – more limiting in most cases than CPU speed.  That is why RAID drives (random array of independent disks) were developed.  As flash memory gets cheaper, there will be a time when mass storage is nearly as fast as RAM, but that is still a few years off. 

 

-Rich

 

Sincerely,

Rich Cooper

EnglishLogicKernel.com

Rich AT EnglishLogicKernel DOT com

9 4 9 \ 5 2 5 - 5 7 1 2

---

From: ontolog-forum-bounces@xxxxxxxxxxxxxxxx [mailto:ontolog-forum-bounces@xxxxxxxxxxxxxxxx] On Behalf Of Simon Spero
Sent: Saturday, October 13, 2012 7:45 AM
To: [ontolog-forum]
Subject: Re: [ontolog-forum] [SMW-devel] [News] Google, Microsoft, Facebook And Others Launch SMW site

 

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)