이어지는 예제는 주어진 수가 소수인지 알아보는 간단한 파이썬 기반 알고리즘이다.

def is_prime(number):
    for i in range(2, number):
        if number % i == 0:
          return False
    return True

이 코드는 number를 인수로 받아 2부터 number까지의 모든 수로 number를 나눠서 나머지가 있는지 확인한다. 나머지가 없으면 당연히 이 수는 소수가 아니므로 바로 False를 반환한다. number까지 모두 나눴는데도 항상 나머지가 있으면 이 수는 당연히 소수이므로 True를 반환한다.

이 예제에서는 앞선 예제들과 핵심 질문이 조금 달라진다. 앞선 예제에서는 배열에 데이터 원소가 N개일 때 알고리즘에 몇 단계가 필요한가를 물었다. 여기서는 배열이 아니라 이 함수에 전달하는 number가 대상이다. 전달하는 number가 함수 루프 실행 횟수를 좌우한다.

따라서 예제에 맞는 핵심 질문은 다음과 같다. number에 N을 전달할 때 알고리즘에 몇 단계가 필요할까?

숫자 7을 is_prime에 전달하면 for 루프는 일곱 단계를 실행한다(실제로는 2에서 시작해서 실제 number 바로 전에 끝나므로 다섯 단계를 실행한다). 수가 101이면 루프는 101단계를 실행한다. 함수로 전달된 수에 비례해 단계 수가 증가하므로 전형적인 O(N) 예제다.

다시 말하지만 주요 데이터가 배열이 아닌 수이므로 핵심 질문에서 대상으로 하는 N의 종류가 다르다. 이어지는 장들에서 N을 찾는 연습을 더 해보겠다.