실행하니 다음처럼 출력되었습니다.
elapsed time: 2.24192214012146 elapsed time: 2.5613863468170166
첫 번째 결과는 O(n)의 결과로 2.2초가 나왔습니다. 두 번째는 for 문을 2번 사용한 O(n2)이므로 O(n) 실행 시간인 2.2초의 제곱인 4.8초 정도가 나올 것 같았는데, 실제로는 0.3초 정도만 차이가 나네요. 예상과는 다른 결과입니다. 그럼 입력 개수를 100만 개 정도로 늘려볼까요?
elapsed time: 22.730210065841675 elapsed time: 26.596558094024658
출력 결과를 보니 3~4초 정도만 늘어났습니다. 이 정도도 엄청나게 큰 차이라고 할 수 있지만 n2 연산이라고 하기에는 너무나도 적은 차이입니다. 왜 그럴까요? 코드를 자세히 살펴봅시다.