느린 O(N²) 알고리즘을 빠른 O(N) 알고리즘으로 대체할 수 있는 현실적인 예제를 하나 살펴보자.

사용자가 제품에 대해 1부터 10사이로 매긴 평점을 분석하는 자바스크립트 애플리케이션을 작성하고 있다고 하자. 그중에서도 평점 배열에 중복 숫자가 들어 있는지 확인하는 함수를 작성하고 있다. 이 함수는 향후 소프트웨어의 다른 부분에 들어가 보다 복잡한 계산에 쓰인다.

예를 들어 배열 [1, 5, 3, 9, 1, 4]에는 숫자 1이 두 번 나오므로 true를 반환함으로써 배열에 숫자가 중복으로 들어 있다고 알린다.

머릿속에 가장 먼저 떠오르는 방법 중 하나가 다음과 같이 중첩 루프를 사용하는 것이 아닐까 싶다.

function hasDuplicateValue(array) {
    for(let i = 0; i < array.length; i++) {
        for(let j = 0; j < array.length; j++) { 
            if(i !== j && array[i] === array[j]) {
                return true; 
            }
        } 
    }
    return false; 
}