[xquery-talk] Time complexity of XQuery
Amitabh 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
More information about the talk
mailing list