실제로 O(2ⁿ) 또는 O(n!) 복잡도가 거의 발생하지 않게 하려면 유명한 (또는 악명 높은) 외판원 문제(traveling salesman problem)를 생각해 보라. 이 문제에서 외판원은 많은 도시를 여행해야 하며 각 도시는 한 번씩만 방문해야 한다. 모든 도시는 다른 모든 도시와 직접 연결된다. 풀어야 할 문제는 외판원이 가능한 짧은 거리를 여행하면서 각 도시를 한 번씩만 방문해야 한다는 것이다. 직접적인 해결 방법은 도시들을 대상으로 모든 가능한 순열을 시도하는 것이다. n개의 도시가 있다면 복잡도는 O(n!)이 된다. O(n²2ⁿ)으로 문제를 해결하는 더 나은 알고리즘이 있지만, 실제 차이는 크게 나지 않는다. 그렇다면 이 문제(그리고 비슷한 다른 문제들)를 어떻게 해결할 수 있을까? 명확한 답을 줄 수 있는 좋은 알고리즘은 모르더라도 근접한 결과를 얻을 수 있는 좋은 알고리즘을 찾을 수 있다.

빅오(big O)는 알고리즘의 성능 상한(upper bound)을 말한다. 그 반대인 하한(lower bound)은 알고리즘의 복잡도가 초깃값 이후 언제나 특정 함수보다 더 낫지 않다는 것을 알 때 해당한다. 이를 빅오메가(big Omega) Ω(f(n))이라고 하며, n ≥ n₀인 모든 n에 대해 f(n) ≥ cg(n) ≥ 0을 만족하는 양의 상수 c와 n₀이 있다면 Ω(f(n)) = g(n)으로 정의한다. 빅오와 빅오메가가 정의되면 동시에 상한과 하한의 복잡도 둘 다 되는 상황을 정의할 수 있다. 이것을 빅세타(big Theta)라고 하며, O(f(n)) = g(n)이고 Ω(f(n)) = g(n)면 Ω(f(n)) = g(n)의 필요충분조건이 된다고 말한다. 그러면 알고리즘은 상수로 스케일링 된 같은 함수로 상한과 하한의 실행 시간을 갖고, 알고리즘의 실행 시간은 해당 함수 주변 범위에 놓인다고 볼 수 있다.