다음 알고리즘에 대한 시간 복잡도는?sum ← 0;for j ← 1 t… | [7급 국가직 알고리즘] 23년 1회차 기출문제 상세 페이지

전체 시간 복잡도는 $O(n^2)$이다.
이중 반복문: 안쪽 반복이 j회씩 실행되므로 $1+2+\cdots+n=\dfrac{n(n+1)}{2}$회
단일 반복문: n회
합계: $\dfrac{n(n+1)}{2}+n$이며 최고차항이 $n^2$이다.
$O(n)$은 뒤쪽 단일 반복문만 센 값으로, 이중 반복을 반영하지 못한다.
$O(n\log_2(n))$는 반복 범위가 절반씩 줄어드는 구조에서 나오며, 여기서 안쪽 반복은 j까지 선형으로 늘어난다.
$O(2^n)$은 지수적 재귀 등에서 나타나며, 다항 횟수만 실행되는 이 코드와 무관하다.