Độ phức tạp

/* O(1): số bước không phụ thuộc n */
int x = a[5];
x = x * 2 + 1;

/* O(n): một vòng lặp chạy n lượt */
for (int i = 0; i < n; ++i) {
    tong += a[i];
}

/* O(n²): hai vòng lồng nhau, mỗi vòng n lượt */
for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
        c[i][j] = 0;
    }
}

/* O(n²): vẫn bậc hai dù vòng trong ngắn dần
   Tổng: n + (n-1) + ... + 1 = n(n+1)/2 */
for (int i = 0; i < n; ++i) {
    for (int j = i; j < n; ++j) {
        lam_gi_do();
    }
}

/* O(log n): biến chạy NHÂN hoặc CHIA mỗi lượt */
for (int i = 1; i < n; i *= 2) {
    lam_gi_do();
}

while (n > 0) {
    n /= 2;
}

/* O(n log n): vòng ngoài n lượt, vòng trong log n lượt */
for (int i = 0; i < n; ++i) {
    for (int j = 1; j < n; j *= 2) {
        lam_gi_do();
    }
}

/* O(n + m): hai vòng NỐI TIẾP, không lồng nhau */
for (int i = 0; i < n; ++i) { lam_a(); }
for (int i = 0; i < m; ++i) { lam_b(); }

O(2n)      ->  O(n)
O(500)     ->  O(1)
O(n / 2)   ->  O(n)
O(3n²)     ->  O(n²)
O(log₂ n)  ->  O(log n)      cơ số không quan trọng

O(n² + n)         ->  O(n²)
O(n² + n³)        ->  O(n³)
O(n + log n)      ->  O(n)
O(n log n + n)    ->  O(n log n)

#include <stdio.h>
#include <time.h>

static long long dem_cap(const int *a, size_t n)
{
    long long dem = 0;

    for (size_t i = 0; i < n; ++i) {
        for (size_t j = i + 1; j < n; ++j) {
            if (a[i] + a[j] == 100) {
                ++dem;
            }
        }
    }

    return dem;
}

int main(void)
{
    static int a[40000];

    for (size_t i = 0; i < 40000; ++i) {
        a[i] = (int)(i % 100);
    }

    for (size_t n = 5000; n <= 40000; n *= 2) {
        clock_t t0 = clock();

        /* Phải DÙNG kết quả, nếu không ở mức -O2 trình biên dịch
           thấy nó bị vứt đi và xóa luôn cả hai vòng lặp. */
        long long kq = dem_cap(a, n);

        double giay = (double)(clock() - t0) / CLOCKS_PER_SEC;

        printf("n = %6zu  ->  %.3f giây  (đếm được %lld cặp)\n",
               n, giay, kq);
    }

    return 0;
}

/* O(1) bộ nhớ phụ: chỉ vài biến, không phụ thuộc n */
long long tong(const int *a, size_t n)
{
    long long s = 0;

    for (size_t i = 0; i < n; ++i) {
        s += a[i];
    }

    return s;
}

/* O(n) bộ nhớ phụ: cấp một mảng mới cỡ n */
int *sao_chep(const int *a, size_t n)
{
    int *b = malloc(n * sizeof *b);

    for (size_t i = 0; i < n; ++i) {
        b[i] = a[i];
    }

    return b;
}

/* O(n) bộ nhớ phụ dù không có malloc:
   mỗi lời gọi đệ quy chiếm một khung trên ngăn xếp */
long long giai_thua(int n)
{
    if (n <= 1) {
        return 1;
    }

    return n * giai_thua(n - 1);
}