MembershipUserCollection membershipUsers = new MembershipUserCollection();
users.ToList().ForEach(membershipUsers.Add); //what is the complexity of this line?
There are very, very few guarantees, but there are a few optimizations:
- Extension methods that use indexed access, such as
ElementAt,Skip,LastorLastOrDefault, will check to see whether or not the underlying type implementsIList<T>, so that you get O(1) access instead of O(N). - The
Countmethod checks for anICollectionimplementation, so that this operation is O(1) instead of O(N). Distinct,GroupByJoin, and I believe also the set-aggregation methods (Union,IntersectandExcept) use hashing, so they should be close to O(N) instead of O(N²).Containschecks for anICollectionimplementation, so it may be O(1) if the underlying collection is also O(1), such as aHashSet<T>, but this is depends on the actual data structure and is not guaranteed. Hash sets override theContainsmethod, that's why they are O(1).OrderBymethods use a stable quicksort, so they're O(N log N) average case.
http://stackoverflow.com/questions/2799427/what-guarantees-are-there-on-the-run-time-complexity-big-o-of-linq-methods
