What's the complexity of containsObject in NSArray

http://developer.apple.com/library/mac/#documentation/Cocoa/Refer开发者_运维技巧ence/Foundation/Classes/NSArray_Class/NSArray.html

Is it O(n) or O(log n)

The documentation you linked to answers the question:

This method determines whether anObject is present in the array by sending an isEqual: message to each of the array’s objects (and passing anObject as the parameter to each isEqual: message).

So containsObject iterates over each of the array's objects, which is an O(n) operation. (Presumably the algorithm stops if it finds a match, so it would test n / 2 objects on average.)