> So the total number of namespace nodes is roughly O(N^2), 
> where N is the average depth of the stylesheet's xml tree.

I would say it is O(N*M) where N is the number of elements in the document
and M is the number of namespaces.

Michael Kay
http://www.saxonica.com/