Time complexity of XQueryAmitabh Ojha amitabhojha at rediffmail.com
Tue Feb 22 10:04:52 PST 2005
Dear members, I invite your attention to the following XML document, data.xml : <?xml version="1.0"?> <KMeansData> <Object> <X>41</X> <Y>3</Y> </Object> <Object> <X>65</X> <Y>16</Y> </Object> <Object> <X>10</X> <Y>20</Y> </Object> </KMeansData> Also, pl see the following query : let $x := doc (data.xml)/KMeansData/Object for $y in $x return ($y/X, $y/Y) If n be the number of elements named Object in the XML file above, then would the time complexity of the XQuery above be O(n) or O(n^2) ? I am asking this question because while using a particular XQuery Engine, I did an experiment with synthetically generated XML data for upto n = 10,000. While the time remained O (n) i.e linear upto n = 7,000 but after that, I noticed a tendency towards O(n^2). Will appreciate your comments/ help. Amitabh Ojha -------------- next part -------------- An HTML attachment was scrubbed... URL: http://xquery.com/pipermail/talk/attachments/20050222/74bcd1cc/attachment.htm
PURCHASE STYLUS STUDIO ONLINE TODAY!
Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced!
Download The World's Best XML IDE!
Accelerate XML development with our award-winning XML IDE - Download a free trial today!
Subscribe in XML format