O
- 주어진 함수의 상한
- 함수의 성장 속도가 특정 함수보다 같거나 느림
Ω
- 주어진 함수의 하한
- 함수의 성장 속도가 특정 함수보다 같거나 빠름
- 표현된 시간복잡도보다 실제 코드 실행에 걸리는 시간이 더 오래 걸리게 되는 위험 有
Θ
- 주어진 함수의 정확한 성장
- 함수의 성장 속도가 특정 함수와 동일함
- 현실적으로 특정 코드의 시간 복잡도를 완벽하게 알기 힘든 경우 多
Tips
1. x를 무한히 크게 만들었을 때, 모든 다항식은 로그함수 식보다 크다.
