Документация, на которую вы ссылаетесь, отвечает на вопрос:
Этот метод определяет, присутствует ли anObject в массиве, отправляя сообщение isEqual: каждому из объектов массива(и передача anObject в качестве параметра для каждого isEqual: сообщения).
Таким образом, containsObject выполняет итерацию по каждому из объектов массива, что является операцией O (n),(Предположительно алгоритм останавливается, если находит совпадение, поэтому он в среднем будет тестировать n / 2 объектов.)