빅오 표기법

// O(1) : constant time
F(int[] n) {
    return (n[0] == 0) ? true : false;
}

// O(n) : linear time
F(int[] n) {
    for i = 0 to n.length
        print i
}

// O(n^2) : quadratic time
F(int[] n) {
    for i = 0 to n.length
        for j = 0 to n.length
            print i + j;
}

// O(nm) : quadratic time
F(int[] n, int[] m) {
    for i = 0 to n.length
        for j = 0 to m.length
            print i + j;
}

// O(n^3) : polynomial / cubic time
F(int[] n) {
    for i = 0 to n.length
        for j = 0 to n.length
            for k = 0 to n.length
                print i + j + k;
}

// O(2^n) : exponential time
ex) Fibonacci
F(n, r) {
    if (n <= 0) return 0;
    else if (n == 1) return r[n] = 1;
    return r[n] = F(n - 1, r) + F(n - 2, r);
}

// O(m^n)

// O(log n)
ex) binary search
F(k, arr, s, e) {
    if (s > e) return -1;
    m = (s + e) / 2;
    if (arr[m] == k) return m;
    else if (arr[m] > k) return F(k, arr, s, m-1);
    else return F(k, arr, m+1, e);
}

// O(sqrt(n))

// Drop constants

* 빅오표기법은 실제 시간이 아니라 데이터량에 따른 시간 복잡도에 대한 표기법