O(1)
상수
입력 크기와 무관하게 일정한 횟수로 끝난다. 배열 인덱스 접근이나 변수 비교가 여기에 가깝다.
복잡도는 입력이 커질 때의 증가 속도다
Big-O는 큰 입력에서 성능을 지배하는 항만 남겨, 코드가 버틸 수 있는 입력 규모를 미리 가늠하게 해준다. 상수항을 버리더라도 실제 제출에서는 제한 시간, 메모리, 자료구조 비용까지 함께 읽어야 한다.
O(log N)
절반씩 감소
이진 탐색처럼 후보를 빠르게 줄인다. 단, 정렬이나 단조 조건이 먼저 있어야 한다.
O(N)
한 번 순회
입력 개수만큼 작업이 늘어난다. 한 번 순회와 해시 카운팅이 대표적이다.
O(N²)
쌍 비교
이중 루프처럼 입력 증가가 제곱으로 커진다. N이 10만이면 거의 항상 다른 접근이 필요하다.