입력 크기

알고리즘의 빠르기는 입력 크기 n 의 함수로 잰다. 수 N 의 입력 크기는 N 자체가 아니라 N 을 적는 자릿수(이진법으로 약 log₂ N 비트)이고, 그래프라면 꼭짓점과 변의 수에 비례한다. 이 구분은 중요하다. N 을 √N 까지 차례로 나눠 보는 인수분해는 N 에 견주면 빨라 보이지만, 자릿수 n 으로 재면 약 2^(n/2) 단계가 드는 지수 시간 방법이다.