rust-lang/rust — pull request #16267 by Gankro (2014-08-05 14:13:14+00:00)
Title: add discussion of performance analysis to libcollection

This was partially inspired by the [excellent documentation](http://qt-project.org/doc/qt-4.8/containers.html) Qt provides for its Container library. This is effectively Part-0 of my plan to provide performance details for all of the collection classes. It intends to provide a simple background on theoretical performance analysis, while noting that theory and practice may diverge. I'd like to eventually provide high-level discussions of when to use (or not use) each collection, as well as document the asymptotic performance of each collection's operations.

I probably go too in-depth on Big-Oh notation, but I do try to be informal about it (since I consider the formal definition largely immaterial to practical usage).

cc @steveklabnik