时间复杂度 - Big O

练习时间复杂度

---

void print(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = i + 1; j < arr.length; j++) {
            System.out.println(arr[j]);
        }
    }
}

O(N^2)
not because there is two for loop

---

void print(int[] arrA, int[] arrB) {
    for (int i = 0; i < arrA.length; i++) {
        for (int j = 0; j < arrB.length; j++) {
            if (arrA[i] < arrB[j]) {
                System.out.println(arrA[i] + "," + arrB[j]);
            }
        }
    }
}

O(N × M)
N = arrA.length, M = arrB.length

---

void print(int[] arrA, int[] arrB) {
    for (int i = 0; i < arrA.length; i++) {
        for (int j = 0; j < arrB.length; j++) {
            for (int k = 0; k < 10000000; k++) {
                System.out.println(arrA[i] + "," + arrB[j]);
            }
        }
    }
}

O(N × M)
N = arrA.length, M = arrB.length

---

// Node { Node right; Node left; int value }
int sum(Node node) {
    if (node == null) {
        return 0;
    }
    return sum(node.left) + node.value + sum(node.right);
}

O(N)
N = number of nodes

---

boolean isPrime(int n) {
    for (int x = 2; x * x < n; x++) {
        if (n % x == 0) {
            return false;
        }
    }
    return true;
}

O(√N)

---

int factorial(int n) {
    if (n < 0) {
        return -1;
    } else if (n == 0) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

O(N)

---