앞서 살펴본 프로세스들에서 어느 프로세스냐에 따라 계산 자원이 선형으로 비례하거나 지수 비례했는데 이를 견주고 싶을 때, 프로세스가 자라나는 정도(order of growth) 라는 개념을 사용한다.
어떻게?
문제의 크기를 매개변수 n이라 할 때, n만큼 큰 문제를 푸는 데 드는 자원 양을 R(n) 이라 하자.
n이 적당히 큰 수일 때, n과 관련 없는 상수 k1, k2에 대해서 다음 조건을 만족한다면, R(n) 은 theta of f(n)이라 한다.
> k1f(n) <= R(n) <= k2f(n)
theta of f(n)
f(n) 이 1000n^2 이든, n^2 이든, 3n^2 + 2N + 1 이든, theta of n^2 라고 표현되므로, 실제 관측값을 나타내는 것은 아니다.
문제의 크기가 커짐에 따라 증가하는 계산량, 메모리 공간 등을 어림잡는 데 유용하게 사용된다.