[xquery-talk] Time complexity of XQuery
amitabhojha at rediffmail.com
Tue Feb 22 10:04:52 PST 2005
I invite your attention to the following XML document, data.xml :
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.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the talk