다음 C 언어로 작성된 코드의 시간 복잡도는? (단, n은 임의의 양의 정수이다)

문제 풀이 참고 자료크게 보기 ↗

1. 1

   Θ(n)

   정답 근거바깥 반복문은 n회, 안쪽 반복문은 고정된 500회 실행됩니다. 상수 500을 제거하면 전체 시간 복잡도는 Θ(n)입니다.
2. 2

   Θ(n²)

   오답 이유안쪽 반복 횟수가 n이 아니라 500으로 고정되어 있으므로 Θ(n²)이 아닙니다.
3. 3

   Θ(log n)

   오답 이유반복 변수가 매회 절반으로 줄어드는 구조가 아니므로 Θ(log n)이 아닙니다.
4. 4

   Θ(n log n)

   오답 이유정렬처럼 n개 원소마다 로그 단계가 필요한 구조가 아니므로 Θ(n log n)이 아닙니다.