Whilst doing some revision for an exam I had to refresh myself on Big-Oh notation which showed me how much is taken for granted by documentation writers.
I refer of course to MSDN, which there appears to be little reference to this notation - the notable exception being "An Extensive Examination of Data Structures". Why does this matter? well if you are trying to work out what the order of magnitude of your code is then you need to know what the underlying framework is doing.
IMHO the collections classes and other such constructs should have their Big-Oh documented against them in the class library.