증가율(growth rate)입력이 커질 때 연산 수가 늘어나는 양상이다.

두 배 입력의 비율T(2n)/T(n)은 입력을 두 배로 늘린 영향을 수로 보여 준다.

교차점계수 때문에 작은 입력의 순서는 큰 입력의 순서와 다를 수 있다.

한 입력에서 값과 증가를 함께 읽는다

세로축은 큰 값도 한 화면에 담기 위한 로그 눈금이다. 표는 실제 함수값을 유지한다.

입력 크기 n

32

표시할 함수

1log₂ nnn log₂ nn²2ⁿ

함수	T(n)	T(2n)	T(2n)/T(n)

계수가 교차점을 옮긴다

an과 bn log₂ n은 a = b log₂ n에서 만난다. 위와 같은 n을 사용해 교차점 앞뒤의 순서를 비교한다.

선형 계수 a

15

n log₂ n 계수 b

2.00