(알고리즘) 동적 배열 append가 O(1)이라는데 가끔 엄청 느려요, 왜죠?

파이썬 list.append나 자바 ArrayList.add 보면 문서에 평균 O(1)이라고 적혀 있잖아요. 근데 실제로 계속 넣다 보면 어떤 순간에 확 느려지는 게 프로파일러에 잡히더라고요. 상수 시간이면 항상 똑같이 빨라야 하는 거 아닌가 싶어서요.

제가 이해한 걸로는 배열이 꽉 차면 새 공간을 잡아서 기존 걸 다 복사한다는데, 그럼 그 순간은 O(n)이잖아요. 근데 왜 평균은 O(1)이라고 부르는 건지가 헷갈립니다.

대충 이런 그림으로 이해하고 있는데 맞나요.

capacity 4 -> 꽉 참 -> capacity 8 새로 잡고 4개 복사
capacity 8 -> 꽉 참 -> capacity 16 새로 잡고 8개 복사

재할당이 매번 일어나는 게 아니라 가끔만 일어나는 건 알겠는데, 이걸 "평균 상수"라고 부르는 근거를 좀 명확하게 알고 싶어요. 그냥 "드무니까 무시"인 건지, 아니면 수학적으로 계산이 딱 떨어지는 건지 궁금합니다. 아는 분 설명 좀 부탁드려요.