I cannot find any data on complexity of underscore's functions, at least nothing can be found on the official Underscore.js site; internet search is also empty. Are there any useful hints short of plodding through the source code?
P.S. Would be nice (but not necessary at the moment) to have such info for other node.js libraries.
P.P.S. Thanks to @generalhenry, a drop-in replacement has been found (lo-dash). Although it seems to be faster, details of its asymptotic complexity (and that of underscore) remain unknown.