위 함수는 변수 i를 사용해 배열 내 각 원소를 순회한다. 이어서 i 내에서 각 값을 살펴야 하므로 변수 j로 배열 내 모든 값을 돌아보는 두 번째 for 루프를 실행하고 i와 j 인덱스에 있는 두 값이같은지 확인한다. 같다면 중복 값을 찾았다는 의미이니 true를 반환한다. 루프를 모두 실행했는데 어떤 중복 값도 찾지 못했다면 배열에 중복이 없음을 알았으니 false를 반환한다.

위 코드가 당연히 잘 동작하긴 하지만 과연 효율적일까? 빅 오 표기법을 조금 배웠으므로 한 발짝 물러나서 이 함수를 빅 오로 어떻게 표현하는지 알아보자.

빅 오는 데이터 값 N개에 비례해 알고리즘에 얼마나 많은 단계가 필요한지를 표현했다. 빅 오를 위 코드에 적용하려면 이렇게 물어야 한다. hasDuplicateValue 함수에 값 N개를 포함하는 배열이 주어졌을 때, 최악의 시나리오에서 알고리즘에 얼마나 많은 단계가 필요한가?

이 질문에 답하려면 먼저 어떤 단계가 필요한지, 그리고 최악의 시나리오는 어떤 경우인지 분석해야 한다.

이 함수에는 한 종류의 단계, 즉 비교가 있다. 함수는 반복해서 i와 j를 비교함으로써 같은지, 즉 중복 쌍인지 확인한다. 최악의 시나리오는 배열이 중복 값을 포함하지 않는 경우다. 이 경우 코드는 false를 반환하기 전에 모든 루프를 수행해야 하고 가능한 모든 조합을 전부 비교해야 한다.

결론적으로 배열에 값 N개가 있을 때 함수는 N²번의 비교를 수행할 것이다. 바깥 루프는 배열을 전부 살펴보기 위해 무조건 N번을 순회해야 하고, 순회마다 안쪽 루프는 다시 N번을 순회해야 하기 때문이다. 이는 N단계 × N단계, 바꿔 말해 N²단계이므로 O(N²)의 알고리즘이다.