알고리즘 분석의 목표는 알고리즘 사이에 의미 있는 비교를 하는 것이지만, 몇 가지 문제점도 있다.

• • 알고리즘의 상대적인 성능은 하드웨어의 특성에 따라 달라질 수 있다. 즉, 어떤 알고리즘이 머신 A에서 더 빠를 수 있고, 머신 B에서는 다른 알고리즘이 더 빠를 수도 있다. 이 문제에 대한 일반적인 해법은 머신 모델을 지정하고, 단계 또는 연산의 개수를 분석하는 것이다. 주어진 모델에 따라 알고리즘은 달라진다.
• • 상대적인 성능은 데이터셋의 성격에 따라 달라진다. 예를 들어 어떤 정렬 알고리즘은 데이터가 어느 정도 정렬되어 있을 때 더 빠르게 동작하는가 하면 어떤 알고리즘은 이런 조건에서 더 느리게 동작한다. 이러한 문제를 해결하는 일반적인 방법은 최악의 경우(worst-case) 시나리오를 분석하는 것이다. 평균의 경우(average-case)를 분석하는 것보다 최악의 경우를 분석하는 것이 유용할 수 있지만, 일반적으로 분석하기가 더 어렵다. 어떤 케이스 집합이 평균 이상인지 명확하지 않을 수 있기 때문이다.
• • 상대적인 성능은 문제 크기에 따라서도 달라진다. 작은 리스트에 대해서 빠르게 동작하는 정렬 알고리즘이 긴 리스트에 대해서는 느리게 동작하기도 한다. 이 문제에 대한 일반적인 해법은 문제의 크기를 함수로 하는 실행 시간을 표현하고, 문제 크기가 증가할 때 실행 시간이 얼마나 빨리 증가하는지에 따라 함수를 카테고리로 분류하는 것이다.

이렇게 비교할 때의 장점은 알고리즘을 간단하게 분류하기에 좋다는 것이다. 예를 들어 알고리즘 A의 실행 시간이 입력 크기 n에 비례하고, 알고리즘은 B의 실행 시간이 입력 크기 n2에 비례한다는 것을 알고 있다면 n 값이 충분히 클 때 A가 B보다 더 빠르다고 예상할 수 있다.

이러한 분석 방법은 몇 가지 결점이 있지만, 이에 대해서는 나중에 살펴보겠다.