알고리즘 시간 복잡도 Big-O 표기법

점근적 상한은 입력 크기 n이 충분히 커질 때, 알고리즘의 실행 시간이나 사용 공간이 특정 함수 g(n)의 상수 배를 넘지 않는다는 개념을 나타낸다. Big-O 표기법은 이 점근적 상한을 수학적으로 정의하는 도구이다. 공식적으로, 어떤 함수 f(n) = O(g(n))이라는 것은 모든 충분히 큰 n에 대해 f(n) ≤ c * g(n)을 만족하는 양의 상수 c가 존재함을 의미한다[2].

이 개념은 알고리즘의 효율성을 입력 크기의 증가에 따른 추세로 이해하는 데 핵심적이다. 예를 들어, 실행 시간이 O(n²)인 알고리즘은 입력이 커질수록 실행 시간이 최대 n²에 비례하여 증가한다는 보장을 제공한다. 이때 중요한 것은 '상한'이라는 점으로, 알고리즘이 실제로는 더 빠르게 동작할 수 있지만, Big-O 표기법은 그 성능이 결코 이 한계보다 나빠지지 않음을 설명한다.

점근적 분석은 낮은 차수의 항과 상수 계수를 무시하며, 장기적인 성장 추세에만 집중한다. 따라서 알고리즘의 실행 시간을 5n² + 3n + 20과 같이 표현했을 때, Big-O 표기법에서는 지배적인 항인 n²만을 고려하여 O(n²)으로 단순화한다. 이 접근법은 서로 다른 알고리즘을 동일한 기준으로 비교하고, 입력 크기가 매우 클 때의 상대적 효율성을 예측하는 강력한 틀을 제공한다.

알고리즘 분석에서 최악의 경우 분석은 입력 크기 n에 대해 알고리즘이 수행할 수 있는 최대의 연산 횟수 또는 최장의 실행 시간을 의미하는 시나리오를 고려하는 방법이다. 이 분석의 결과는 Big-O 표기법으로 표현되어 알고리즘의 성능 상한을 제공한다. 예를 들어, 선형 검색 알고리즘은 찾고자 하는 값이 배열의 맨 끝에 있거나 배열에 존재하지 않을 때, 모든 요소를 한 번씩 검사해야 하므로 최악의 경우 시간 복잡도는 O(n)이 된다.

최악의 경우 분석은 알고리즘의 성능이 결코 이 한계를 넘지 않음을 보장하기 때문에, 특히 시스템의 응답 시간이나 자원 사용량에 대한 신뢰성 있는 예측이 필요한 분야에서 중요하게 여겨진다. 실시간 시스템이나 안전-중요 시스템에서는 최악의 경우 실행 시간이 제한 시간 내에 완료됨을 보장해야 하므로, 이 분석 방식이 필수적이다.

다음은 몇 가지 알고리즘의 최악의 경우 시나리오와 그에 따른 Big-O 복잡도를 정리한 표이다.

최악의 경우 분석은 알고리즘의 안정성을 평가하는 강력한 도구이지만, 알고리즘이 실제로는 평균적으로 더 좋은 성능을 보일 수 있다는 점을 유의해야 한다. 따라서 종종 평균 경우 분석이나 최선의 경우 분석과 함께 종합적으로 고려되어야 한다.

입력 크기(n)에 관계없이 항상 일정한 실행 시간을 가지는 알고리즘의 시간 복잡도를 상수 시간 또는 O(1)이라고 부른다. 여기서 '1'은 상수를 의미하며, 입력이 아무리 커져도 알고리즘의 수행 시간이 변하지 않음을 나타낸다.

상수 시간 연산의 전형적인 예로는 배열의 인덱스를 사용한 접근, 사전(해시 테이블)에서의 키 조회, 두 변수의 값 교환(스왑) 등이 있다. 아래는 몇 가지 O(1) 연산의 예시이다.

이러한 연산들은 데이터의 크기나 개수와 무관하게 항상 고정된 수의 기본 연산만을 수행한다. 예를 들어, 크기가 10인 배열의 첫 번째 요소를 읽는 시간과 크기가 100만인 배열의 첫 번째 요소를 읽는 시간은 동일하다. 이는 메모리 주소를 통해 직접 접근할 수 있기 때문이다.

따라서 시간 복잡도 분석에서 O(1)은 가장 효율적인 등급에 속한다. 알고리즘 설계 시 가능한 많은 부분을 상수 시간 내에 처리하도록 구성하는 것이 성능 최적화의 중요한 목표가 된다. 그러나 전체 알고리즘의 복잡도는 가장 느린 부분에 의해 결정되므로, O(1) 연산이 포함되었다고 해서 전체 알고리즘이 O(1)이 되는 것은 아니다.

로그 시간 복잡도 O(log n)는 입력 크기 n에 대해 실행 시간이 로그 함수에 비례하여 증가하는 것을 의미한다. 여기서 로그의 밑은 보통 2이며, 컴퓨터 과학에서는 이진 탐색과 같은 알고리즘에서 흔히 나타난다. 입력 데이터가 두 배로 증가해도 실행 시간은 고정된 상수만큼만 증가하는 매우 효율적인 성장률을 보인다.

이 복잡도의 대표적인 예는 이진 탐색 알고리즘이다. 정렬된 배열에서 특정 값을 찾을 때, 배열의 중간 값을 확인하고 찾는 값과 비교한다. 비교 결과에 따라 탐색 범위를 절반으로 줄여나가며, 매 단계마다 검사해야 할 데이터의 양이 기하급수적으로 감소한다. 따라서 최대 비교 횟수는 log₂ n을 넘지 않는다. 균형 이진 탐색 트리에서의 탐색 연산도 동일한 원리로 O(log n)의 시간이 소요된다.

로그 시간 복잡도를 가지는 다른 알고리즘으로는 특정 조건 하의 유클리드 호제법(최대공약수 계산)이나 힙 자료구조에서의 삽입 및 삭제 연산이 있다. 또한 효율적인 정렬 알고리즘인 퀵 정렬과 병합 정렬의 평균 시간 복잡도 O(n log n)에도 로그 요소가 포함되어 있다. 이는 분할 정복 패러다임에서 문제를 지속적으로 절반으로 나누는 과정에서 기인한다.

로그 시간 복잡도는 입력이 매우 커질수록 그 효율성이 두드러진다. 예를 들어, 100만 개의 데이터에서 특정 항목을 찾는 데 선형 탐색은 최대 100만 번의 비교가 필요하지만, 이진 탐색은 약 20번의 비교만으로 동일한 작업을 수행할 수 있다.

입력 크기 n에 비례하여 실행 시간이 선형적으로 증가하는 알고리즘의 복잡도를 선형 시간 복잡도라고 하며, Big-O 표기법으로 O(n)으로 표현한다. 이는 알고리즘이 각 입력 요소를 정확히 한 번씩 처리하는 경우에 해당하는 일반적인 패턴이다.

대표적인 예로, 크기가 n인 배열의 모든 요소를 한 번 순회하며 출력하는 단일 for 루프가 있다. 이 경우 루프는 n번 반복되며, 각 반복에서의 연산은 상수 시간이 소요되므로 전체 시간 복잡도는 O(n)이 된다. 마찬가지로, 선형 검색 알고리즘도 최악의 경우 목표 값을 찾기 위해 리스트의 처음부터 끝까지 모든 요소를 확인해야 하므로 O(n)의 복잡도를 가진다.

O(n) 복잡도는 입력이 증가함에 따라 실행 시간이 직선적으로 증가하는 양상을 보인다. 이는 상수 시간(O(1))보다는 덜 효율적이지만, 이중 for 루프로 인한 O(n²)나 지수 시간 복잡도보다는 훨씬 효율적인 것으로 평가된다. 많은 기본적인 데이터 처리 작업이 이 범주에 속하며, 알고리즘 설계에서 바람직한 목표 중 하나이다.

선형 로그 시간은 입력 크기 n에 대해 실행 시간이 n * log n에 비례하는 알고리즘의 성능을 나타낸다. 이 복잡도는 효율적인 정렬 알고리즘과 분할 정복 알고리즘에서 흔히 나타난다. O(n log n)은 선형 시간 O(n)보다는 느리지만, 다항 시간 O(n²)보다는 훨씬 빠른 성능을 보인다. 대규모 데이터를 처리할 때 선형 로그 시간 알고리즘의 효율성은 매우 중요해진다.

대표적인 예로 병합 정렬, 힙 정렬, 그리고 대부분의 경우 퀵 정렬이 O(n log n)의 시간 복잡도를 가진다. 이러한 알고리즘들은 데이터를 반복적으로 절반으로 나누어(log n 단계) 처리한 후, 결과를 선형 시간(n)에 결합하는 방식으로 동작한다. 예를 들어, 병합 정렬은 배열을 재귀적으로 분할한 후, 정렬된 부분 배열들을 병합하는 과정에서 이 복잡도가 발생한다.

O(n log n) 복잡도의 다른 예시로는 효율적인 비교 정렬 알고리즘의 이론적 하한[5]을 만족하는 알고리즘들, 그리고 이진 탐색 트리에서의 모든 노드 순회(중위 순회) 등이 있다. 아래는 흔히 접하는 시간 복잡도들의 성능 비교를 보여준다.

실제 실행 시간은 상수 계수와 하드웨어 성능에 영향을 받지만, 알고리즘의 확장성을 평가할 때 O(n log n)은 매우 우수한 축에 속한다. 데이터 양이 두 배로 늘어나면 실행 시간은 "2 * (log(2n)/log(n))"배, 즉 2배보다 약간 더 늘어나는 수준이기 때문이다.

다항 시간(Polynomial Time) 복잡도는 입력 크기 n에 대한 다항식 함수로 표현되는 실행 시간을 의미한다. 가장 흔한 예시로 이차 시간(O(n²))과 삼차 시간(O(n³))이 있으며, 이들은 일반적으로 비효율적인 알고리즘으로 분류된다.

O(n²) 복잡도를 가지는 알고리즘의 전형적인 예는 이중 중첩 반복문을 사용하는 경우이다. 예를 들어, 크기가 n인 배열의 모든 원소 쌍을 비교하는 버블 정렬이나 선택 정렬과 같은 단순 정렬 알고리즘이 이에 해당한다. 입력 크기가 커질수록 실행 시간은 제곱에 비례하여 급격히 증가한다. O(n³) 복잡도는 삼중 중첩 반복문에서 나타나며, 예를 들어 3차원 데이터를 처리하거나 세 개의 배열을 모두 순회하는 알고리즘에서 볼 수 있다.

이러한 다항 시간 알고리즘은 지수 시간이나 계승 시간 알고리즘보다는 효율적이지만, 입력이 매우 커지면 실용적이지 않을 수 있다. 특히 O(n³) 이상의 고차 다항식 복잡도를 가진 알고리즘은 대규모 데이터 처리에 부적합하다. 그러나 다항 시간은 계산 복잡도 이론에서 P 문제 클래스를 정의하는 기준이 되어, NP-완전 문제와 구분하는 중요한 척도가 된다.

지수 시간 복잡도를 가지는 알고리즘은 입력 크기 n이 증가함에 따라 실행 시간이 지수 함수 또는 계승 함수 형태로 폭발적으로 증가합니다. 이는 O(2ⁿ), O(3ⁿ), O(n!) 등으로 표기되며, 다항 시간 알고리즘에 비해 매우 비효율적입니다. 일반적으로 n이 40~50 정도만 되어도 현실적인 시간 내에 계산을 끝내기 어려워지므로, 실용적인 문제 해결에는 부적합한 경우가 많습니다.

O(2ⁿ) 복잡도의 전형적인 예는 모든 부분집합을 생성하는 문제나 피보나치 수를 재귀적으로 계산하는 간단한 알고리즘입니다. 예를 들어, n개의 원소를 가진 집합의 모든 부분집합의 개수는 2ⁿ개입니다. O(n!) 복잡도는 주로 모든 가능한 순열을 나열하는 문제에서 나타납니다. n개의 서로 다른 항목을 일렬로 배열하는 방법의 수는 정확히 n!가지이기 때문입니다. 다음은 대표적인 지수 시간 알고리즘의 예시입니다.

이러한 복잡도의 알고리즘은 입력이 매우 작은 경우에만 사용 가능합니다. 따라서 실무에서는 동적 계획법이나 분기 한정법, 휴리스틱 알고리즘 등을 활용하여 실행 시간을 단축시키는 방법을 모색합니다. 예를 들어, 재귀적 피보나치 알고리즘은 메모이제이션을 적용하면 O(n) 수준으로 복잡도를 낮출 수 있습니다. 지수 시간 알고리즘은 주로 NP-난해 문제나 NP-완전 문제와 연관되어 있으며, 이 문제들의 효율적 해법이 발견되지 않았다는 점은 컴퓨터 과학의 중요한 미해결 문제 중 하나입니다[7].

Big-O 표기법에서 입력 크기 $n$이 충분히 클 때, 알고리즘의 성장률에 가장 큰 영향을 미치는 것은 최고차항이다. 따라서 성능 분석 시 상대적으로 덜 중요한 요소들을 단순화하기 위한 규칙이 적용된다.

계수 법칙은 상수 인자가 점근적 성능에 미치는 영향을 무시한다는 규칙이다. 예를 들어, $O(2n)$이나 $O(\frac{n}{2})$는 모두 $O(n)$으로 단순화된다. 이는 입력 크기가 무한히 커질수록 상수 배수의 차이는 의미를 잃기 때문이다. 마찬가지로, $O(5n² + 3)$에서 상수항 $3$도 무시된다.

이러한 단순화의 핵심은 '지배적 항만 고려하기' 원칙이다. 다항식 시간 복잡도에서 가장 높은 차수의 항이 성장을 지배한다. 예를 들어, $O(3n³ + 20n² + 5n + 10)$은 $O(n³)$으로 표현된다. $n$이 증가함에 따라 $n³$ 항이 다른 모든 항의 합보다 훨씬 빠르게 커지기 때문이다. 이 규칙들은 알고리즘의 근본적인 효율성 클래스를 명확하고 간결하게 비교하는 데 목적이 있다.

두 개 이상의 독립된 연산 단계가 순차적으로 실행될 때, 전체 시간 복잡도는 각 단계의 복잡도를 더하는 합의 법칙에 따라 결정된다. 예를 들어, O(n)의 연산 뒤에 O(n²)의 연산이 이어진다면, 전체 복잡도는 O(n + n²)이 된다. 이후 점근적 표기법 규칙에 따라 지배적인 항만 남기므로, 이 경우 최종적으로 O(n²)으로 단순화된다.

반면, 한 연산 블록이 다른 블록 내에서 반복적으로 실행되는 경우, 즉 중첩되는 경우에는 곱의 법칙이 적용된다. 바깥쪽 루프가 O(n)번 실행되고, 그 안쪽 루프가 O(m)번 실행된다면, 전체 시간 복잡도는 O(n * m)이 된다. 대표적인 예로 이중 for문이 있으며, 입력 크기가 n으로 동일하다면 O(n²)의 복잡도를 가진다.

이 두 법칙을 적용할 때 주의할 점은 연산 단계가 정말로 '독립적'이고 순차적인지, 아니면 '중첩'되어 있는지를 정확히 구분하는 것이다. 아래 표는 몇 가지 일반적인 패턴을 보여준다.

이러한 법칙들은 복잡한 알고리즘을 여러 개의 기본적인 구성 요소로 분해하여 분석할 수 있게 해주는 기초 도구 역할을 한다.

점근적 표기법에서 가장 중요한 규칙 중 하나는 입력 크기 n이 무한히 커질 때, 성장률에 가장 큰 영향을 미치는 지배적 항만을 고려하고 나머지 항과 계수는 무시하는 것이다. 이는 알고리즘의 효율성을 큰 그림에서 비교하기 위한 핵심 원리이다.

예를 들어, 어떤 알고리즘의 연산 횟수를 T(n) = 5n² + 100n + 300 이라는 다항식으로 표현할 수 있다고 가정하자. n이 매우 작을 때는 100n이나 상수항 300의 영향이 상대적으로 클 수 있다. 그러나 n이 점점 커지면(예: n=1000), 5n² 항은 5,000,000에 달하는 반면, 100n 항은 100,000에 불과하다. n이 10,000이 되면 그 차이는 더욱 벌어진다. 따라서 n이 충분히 크다고 가정할 때, 성장률을 지배하는 것은 최고차항인 n² 항이다. 계수 5와 다른 하위 항들은 점근적 분석에서는 무시되며, 이 알고리즘의 시간 복잡도는 O(n²)으로 표기한다.

이 규칙을 일반화하면, 다항식 함수 f(n) = a_k n^k + a_{k-1} n^{k-1} + ... + a_1 n + a_0 에서 시간 복잡도는 최고차항인 O(n^k)으로 결정된다. 마찬가지로, 여러 항의 합으로 이루어진 복잡도에서도 가장 빠르게 증가하는 항이 지배적이다. 예를 들어, O(n! + 2ⁿ + n³)과 같은 복잡도에서는 팩토리얼 항인 n!이 다른 모든 항을 압도하므로, 최종 점근적 상한은 O(n!)이 된다. 이 원칙은 알고리즘의 핵심적인 성장 추세를 파악하고, 다른 알고리즘과의 효율성을 체계적으로 비교하는 데 필수적이다.

단일 반복문의 시간 복잡도는 반복 횟수에 직접적으로 비례한다. 예를 들어, 크기가 n인 배열의 모든 요소를 한 번씩 출력하는 알고리즘은 n번 반복하므로 선형 시간 복잡도인 O(n)을 가진다. 반복문 내부의 연산이 상수 시간 O(1)에 수행된다는 전제 하에, 전체 시간 복잡도는 반복 횟수에 의해 결정된다.

중첩 반복문의 분석은 각 반복문의 반복 횟수를 곱하여 계산한다. 가장 흔한 예는 이중 중첩 반복문으로, 외부 루프가 n번, 내부 루프가 m번 실행되면 시간 복잡도는 O(n * m)이다. 특히 내부 루프가 외부 루프의 현재 인덱스에 의존할 경우 분석이 달라진다. 외부 루프가 n번 실행되고, 내부 루프가 외부 인덱스 i에 대해 i번 실행된다면, 총 연산 횟수는 1부터 n까지의 합인 n(n+1)/2가 된다. Big-O 표기법에서는 최고차항만을 고려하고 계수를 무시하므로, 이 경우의 시간 복잡도는 O(n²)이 된다.

다양한 중첩 패턴에 따른 시간 복잡도를 표로 정리하면 다음과 같다.

반복문의 조건이 변수에 곱하거나 나누는 방식으로 변경될 때는 로그 시간 복잡도가 발생한다. 예를 들어, 반복마다 처리할 데이터의 양이 절반으로 줄어드는 경우(예: 이진 검색), 시간 복잡도는 O(log n)이 된다. 이러한 분석은 반복문이 알고리즘의 실행 흐름을 지배할 때 유효하며, 내부에서 호출되는 함수의 복잡도가 상수가 아닐 경우 이를 함께 고려해야 한다.

재귀 알고리즘의 시간 복잡도를 분석하는 일반적인 방법은 재귀 트리를 그려보거나 점화식을 세워 푸는 것이다. 특히 알고리즘이 자신을 여러 번 호출하는 형태일 때, 점화식을 통해 시간 복잡도를 유도한다. 예를 들어, 입력 크기 n을 절반으로 나누고 두 개의 재귀 호출을 수행하는 병합 정렬의 점화식은 T(n) = 2T(n/2) + O(n)과 같은 형태가 된다.

이러한 점화식을 해결하는 체계적인 방법 중 하나가 마스터 정리이다. 마스터 정리는 특정 형태 T(n) = aT(n/b) + f(n) (여기서 a ≥ 1, b > 1)의 점화식에 대해, f(n)과 n^(log_b a)의 크기를 비교하여 시간 복잡도를 즉시 결정할 수 있는 정리이다. 이 정리는 크게 세 가지 경우로 나뉜다.

마스터 정리는 이진 탐색, 퀵 정렬(평균적인 경우), 병합 정렬 등 많은 분할 정복 알고리즘의 분석에 유용하게 적용된다. 그러나 모든 재귀식이 마스터 정리의 표준 형태에 맞지는 않으므로, 그럴 때는 재귀 트리 방법 등을 사용하여 직접 유도해야 한다.

Big-O 표기법이 알고리즘의 성능에 대한 점근적 상한을 나타낸다면, Big-Ω 표기법(빅 오메가 표기법)은 그 반대로 알고리즘 성능의 점근적 하한(Asymptotic Lower Bound)을 나타낸다. 즉, 입력 크기 n이 충분히 커질 때, 알고리즘의 실행 시간이 최소한 특정 함수의 상수 배 이상으로 증가함을 의미한다. 어떤 알고리즘의 시간 복잡도가 Ω(g(n))이라면, 충분히 큰 n에 대해 실행 시간이 c * g(n)보다 작을 수 없다는 것을 보장한다[11].

이 표기법은 주로 알고리즘의 최선의 경우(Best-Case) 성능을 분석하거나, 특정 문제를 해결하는 데 필요한 최소한의 시간을 논할 때 사용된다. 예를 들어, 비교 기반 정렬 알고리즘은 최선의 경우에도 Ω(n log n)의 시간 복잡도를 가진다는 것이 알려져 있다[12]. 이는 아무리 효율적인 비교 정렬 알고리즘이라도, 최소한 n log n에 비례하는 시간은 필요하다는 것을 의미한다.

Big-O와 Big-Ω의 관계는 다음과 같이 정리할 수 있다. 알고리즘의 실행 시간이 O(g(n))이면서 동시에 Ω(g(n))이라면, 그 실행 시간은 정확히 Θ(g(n))이다. 다음 표는 세 가지 주요 점근적 표기법의 개념을 비교한다.

따라서 Big-Ω 분석은 알고리즘의 이론적 효율성 한계를 이해하거나, 특정 문제의 본질적인 난이도를 규명하는 데 중요한 도구가 된다.

Big-Θ 표기법은 점근적 표기법의 하나로, 알고리즘의 성능에 대한 정확한 한계(Asymptotic Tight Bound)를 나타낸다. 이는 Big-O 표기법이 점근적 상한만을, Big-Ω 표기법이 점근적 하한만을 나타내는 것과 달리, 함수의 증가율이 위와 아래로 모두 같은 상수 배수 내에 묶여 있을 때 사용한다. 즉, 어떤 알고리즘의 실행 시간이 f(n)이라면, 충분히 큰 n에 대해 c1 * g(n) ≤ f(n) ≤ c2 * g(n)을 만족하는 양의 상수 c1, c2가 존재할 때 f(n) = Θ(g(n))이라고 정의한다.

Big-Θ는 알고리즘의 성능을 가장 정밀하게 분류할 수 있는 표기법이다. 예를 들어, 모든 원소를 한 번씩 확인하는 단순 선형 탐색 알고리즘의 최선, 평균, 최악의 경우 시간 복잡도는 모두 Θ(n)이다. 마찬가지로, 중첩된 두 개의 반복문을 사용하는 기본적인 버블 정렬 알고리즘의 시간 복잡도는 Θ(n²)으로 표현된다. 이는 해당 알고리즘의 성능이 n 또는 n²과 정확히 같은 비율로 증가함을 의미한다.

Big-O, Big-Ω, Big-Θ의 관계는 다음과 같이 정리할 수 있다.

따라서 f(n) = Θ(g(n))이라는 것은 동시에 f(n) = O(g(n))이고 f(n) = Ω(g(n))임을 의미한다. 모든 알고리즘에 대해 Big-Θ 표기를 항상 찾을 수 있는 것은 아니다. 예를 들어, 최선의 경우 Ω(1), 최악의 경우 O(n)인 알고리즘은 Θ(1)이나 Θ(n)이라고 단정할 수 없다. Big-Θ는 알고리즘의 성능이 특정 함수의 범위에 '꽉 차게' 존재할 때만 사용할 수 있는 강력한 표현 도구이다.

Big-O 표기법은 입력 크기 n이 커질 때 알고리즘의 실행 시간이 어떻게 증가하는지 그 추세를 설명하는 점근적 표기법이다. 이 표기법은 최고차항의 차수만을 고려하고, 상수 계수와 낮은 차수의 항을 무시한다. 예를 들어, 실행 시간이 정확히 5n² + 3n + 20인 알고리즘은 O(n²)으로 표기된다. 이는 n이 매우 커지면 n² 항이 전체 성장을 지배하게 되고, 상수 5, 3, 20의 영향은 상대적으로 미미해지기 때문이다.

그러나 이론적인 점근적 분석과 실제 실행 시간 사이에는 중요한 차이가 존재한다. O(n) 알고리즘이 O(n²) 알고리즘보다 항상 빠른 것은 아니다. 만약 O(n) 알고리즘의 상수 계수가 매우 크다면(예: 실행 시간이 1000000n), 입력 크기 n이 특정 임계점보다 작은 구간에서는 O(n²) 알고리즘(예: 실행 시간이 n²)보다 느릴 수 있다[14]. 따라서 Big-O 표기법은 주로 매우 큰 입력에 대한 장기적인 성장률을 비교하는 데 유용하며, 작은 입력 크기나 상수 계수가 큰 경우 실제 성능을 완전히 대변하지 못할 수 있다.

실무에서는 알고리즘 선택 시 Big-O 복잡도와 함께 상수 계수의 영향을 고려해야 한다. 메모리 지역성, CPU 캐시 활용도, 프로그래밍 언어의 특성, 하드웨어 아키텍처 등이 상수 계수에 큰 영향을 미친다. 예를 들어, 이론적으로는 느린 O(n²) 버블 정렬이 작은 n에 대해 캐시 효율이 매우 좋은 구현이라면, 이론적으로 빠른 O(n log n) 퀵 정렬이나 힙 정렬보다 실제로 더 빠를 수 있다. 성능이 중요한 시스템에서는 최종 결정 전에 해당 도메인의 일반적인 입력 크기 범위에서 실제 벤치마킹을 수행하는 것이 필수적이다.

공간 복잡도는 알고리즘이 실행되는 동안 필요로 하는 메모리 공간의 양을 입력 크기에 대한 함수로 나타낸다. 시간 복잡도가 실행 시간의 증가 추세를 분석한다면, 공간 복잡도는 메모리 사용량의 증가 추세를 분석한다. 두 복잡도는 알고리즘의 효율성을 평가하는 핵심 척도이며, 종종 트레이드오프 관계에 있다[15].

공간 복잡도 역시 점근 표기법을 사용하여 표현하며, 가장 일반적으로 Big-O 표기법을 사용한다. 예를 들어, 입력 크기 n에 비례하는 배열을 추가로 생성하는 알고리즘의 공간 복잡도는 O(n)이다. 시간과 공간 복잡도는 독립적으로 분석되지만, 알고리즘의 내부 동작을 통해 연결 지을 수 있다. 재귀 호출은 호출 스택에 메모리를 사용하므로, 공간 복잡도에 영향을 미친다. 반면, 입력 데이터를 제자리에서 정렬하는 제자리 알고리즘은 추가 메모리를 거의 사용하지 않아 공간 복잡도가 O(1)인 경우가 많다.

실제 시스템에서는 시간과 공간 자원이 모두 제한적이기 때문에, 알고리즘 선택 시 두 가지 복잡도를 함께 고려해야 한다. 다음 표는 몇 가지 일반적인 관계를 보여준다.

하드웨어의 발전으로 메모리 용량이 증가했지만, 빅 데이터 처리나 임베디드 시스템과 같은 맥락에서는 공간 복잡도가 시간 복잡도 못지않게 중요한 제약 조건으로 작용한다. 따라서 효율적인 알고리즘은 시간과 공간 사용 사이의 적절한 균형을 찾는다.