for문의 시간복잡도는 항상 O(N)이 아니다

for문의 시간복잡도는 반복문의 종료 조건이 몇 번 평가되는가로 결정된다.

문법 자체의 시간 복잡도가 아닌 실제로 몇 번 도는지가 전부이다.

 

예제  1. O(1) 고정 반복

for (int i = 0; i < 100; ++i) {
    work();
}

 

---

예제 2. O(N)

for (int i = 0; i < n; ++i) {
    // n번 실행
}

• i = 0 → n-1
• 실행 횟수 ≈ n
• 시간 복잡도: O(n)

---

예제 3. O(√N)

for (int i = 1; i * i <= n; ++i) {
    // 약 √n번 실행
}

• 종료 조건이 i * i <= n
• i ≈ √n 까지만 증가
• 시간 복잡도: O(√n)

---

예제 4. O(log N)

for (int i = 1; i <= n; i *= 2) {
    // log₂ n번 실행
}

• i가 두 배씩 증가
• 시간 복잡도: O(log n)

---

예제 5. O(n²)

for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j) {
        // n × n
    }

• 시간 복잡도: O(n²)

---

자주 착각하는 포인트

❌ “for문이니까 O(n)”
❌ “i++ 이니까 선형”

✔ 종료 조건 + 증가 규칙이 핵심
✔ 반복 횟수 = 복잡도

---

한 줄 요약

for문의 시간 복잡도는
종료 조건이 허용하는 반복 횟수로 결정된다.

이걸 이해하면 코테에서 O(n) → O(√n)로 줄이는 포인트가 바로 보인다.