하지만 빅오 표기법에서는 실행 시간에 가장 큰 영향을 미치는 항만 표기합니다. 앞의 예시에서 N이 커지면 커질수록 N²의 영향력은 N의 영향력보다 훨씬 커지게 됩니다. 이에 따라 N은 실행 시간에 무시할 수 있는 영향만 미칩니다. 따라서 빅오 표기법에서는 가장 영향력이 큰 항만 남겨 O(N²+N)은 O(N²)으로 표기합니다.

그렇다면 다음 코드의 시간 복잡도는 어떻게 될까요?

int[] arr = ... // 길이가 N인 배열

for (int i = 0; i < arr.length; i++) {
    for (int j = i + 1; j < arr.length; j++) {
        int a = arr[i];
        int b = arr[j];
        System.out.println(a + " + " + b + " = " + (a + b));
    }
}

그이 코드에서 안쪽 for 문은 배열 전체를 돌지 않고 i 값에 따라 순회하는 범위가 정해집니다. i = 0일 때는 배열 전체를 순회하지만, i = arr.length - 1일 때는 전혀 순회하지 않습니다. 반복하는 횟수를 따져 보면 i = 0일 때 N - 1번, i = 1일 때 N - 2번, i = 3일 때 N - 3번 반복합니다. 즉, 전체 반복 횟수는 1부터 N - 1까지 합이 됩니다. 이를 계산하면 (N - 1)×(N - 2) / 2가 되며, 이를 풀어서 나타내면 이 됩니다.