대부분의 리스트 메서드는 선형이지만, 몇 가지 예외가 있다.

• • 리스트의 끝에 원소를 추가하는 것은 평균적으로 상수 시간이다. 이는 공간이 부족할 때 더 큰 위키로 복사가 발생할 때가 있기 때문이지만, n 연산에 대한 전체 시간은 O(n)이므로 각 연산의 평균 시간은 O(1)이다.
• • 리스트의 끝에서 원소를 제거하는 것은 상수 시간이다.
• • 정렬은 O(n log n)이다.

대부분의 사전 연산과 메서드는 상수 시간이지만, 몇 가지 예외가 있다.

• • update의 실행 시간은 인자로 전달된 사전의 크기에 비례한다. 업데이트되는 사전의 크기에는 비례하지 않는다.
• • keys, values, items는 반복자를 반환하는 것이므로 상수 시간이다. 반복자를 사용해서 루프를 한다면 루프는 선형이다.

사전의 성능은 컴퓨터 과학에서 작은 기적 중의 하나라고 할 수 있다. 사전이 어떻게 동작하는지에 대해서는 344쪽의 해시테이블에서 살펴볼 것이다.