Độ phức tạp và cách chọn

/* O(1): số thao tác không phụ thuộc n */
int dau_tien(const int *a, size_t n) { return n ? a[0] : -1; }

/* O(n): một vòng lặp chạy n lần */
long tong(const int *a, size_t n)
{
    long s = 0;

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

    return s;
}

/* O(n^2): hai vòng lồng nhau, mỗi vòng n lần */
int co_cap_bang_nhau(const int *a, size_t n)
{
    for (size_t i = 0; i < n; ++i)
        for (size_t j = i + 1; j < n; ++j)
            if (a[i] == a[j]) return 1;

    return 0;
}

/* O(log n): mỗi bước chia đôi phạm vi */
size_t tim_nhi_phan(const int *a, size_t n, int x);

/* O(n log n): vòng ngoài n lần, mỗi lần gọi một việc O(log n) */
void chen_het_vao_cay(BST *t, const int *a, size_t n)
{
    for (size_t i = 0; i < n; ++i) bst_chen(t, a[i]);
}

/* O(n + m): hai vòng lặp NỐI TIẾP, không lồng nhau */
void in_hai_mang(const int *a, size_t n, const int *b, size_t m)
{
    for (size_t i = 0; i < n; ++i) printf("%d ", a[i]);
    for (size_t j = 0; j < m; ++j) printf("%d ", b[j]);
}

/* Thuật toán A: O(n^2) với hằng số 1
   Thuật toán B: O(n log n) với hằng số 100

   n = 10   : A = 100,        B = 3320      -> A nhanh hơn 33 lần
   n = 100  : A = 10000,      B = 66400     -> A nhanh hơn 6.6 lần
   n = 1000 : A = 1000000,    B = 996000    -> hòa
   n = 10000: A = 100000000,  B = 13300000  -> B nhanh hơn 7.5 lần

   Điểm hòa vốn ở khoảng n = 1000. Dưới ngưỡng đó, thuật toán
   "tệ hơn về tiệm cận" lại nhanh hơn thật. */