Complexity Examples

Example 1:

for (int i = 0; i < len; i++) {
    for (int j = i + 1; j < len; j++) { O(1)}
}

i = 0; j = 1..n - 1; n - 1. i = 1, j = 2 ... n - 1;n - 2; i = 2, j = 3 ... n - 1; n - 3; i = n - 1; j = n .. n - 1; 1

1 + 2 +... + (n - 1) --> (1 + n - 1)(n - 1) / 2 -->O(n^2)

2Strings: O(ab)

for (int i = 0; i < alen; i++) {
    for (int j = 0; j < blen; j++) {O(1)}
}

Simplify:

O(N+P), p < 2/N. --> O(N); O(N+M) cannot simplify as dunno M; O(N + logN) --> O(N)

Sort array of strings: O(AS(logA+logS))

Given a string array. sort each string (max length is S) in the array, then sort entire array with A strings.

longest string length = s, then sort a string is slogs. array length = A, then takes A*SlogS
array length = A. compare A strings takes AlogA. each string length s. then takes S*AlogA

BT node sum: O(2^depth) = O(2^logn) = O(n)

if (node == null) return 0;
return sum(node.left) + node.val + sum(node.right);
// There are N nodes in the BST and need to iterate through each once

Factorial: O(n)

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

Div: O(a/b)

int div (int a, int b) {
    int count = 0, sum = b;
    while (sum <= a) {
        sum += b;
        count++;
    }
    return count;
}

sum = b; sum <= a, every time sum increment by b, until (b * b *....) <= a b * (a / b) <= a

Permutation 8: O(n!)

void permutation (String str) {permutation(str, "");}
void permutation (String str, String prefix) {
    if (str.length() == 0) print "";
    for (int i = 0; i < str.length(); i++) {
        String rem = str.substring(0, i) + str.substring(i+1);
        permutation(rem, prefix + str.charAt(i));
    }
}

Fib recursion: O(2^n)

int fib (int n) {
    if (n <= 0) return 0;
    else if (n == 1) return 1;
    else return fib(n - 1) + fib(n - 2);
}
// Every split divide into 2 tree branches

All Fib: O(2 ^ n)

void allFib(int n) {
    for (int i = 0; i < n; i++) {
        print fib(i);
    }
}
// 2^1 + 2^2 + .... + 2 ^ (n-1) --> 2^(n+1) --> O(2^(n))

All Fib Smart: O(n)

void allFib (int n) {
    int[] memo = new int[n + 1];
    for (int i = 0; i < n; i++) {
        fib(i, memo);
    }
}
int fib (int n, int[] memo) { // --> O(1)
    if (n <= 0) return 0;
    if (n == 1) return 1;
    if (memo[n] > 0) return memo[n];
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
    return memo[n];
}

Power of 2: O(logn)

int powersOf2 (int n) {
    if (n == 1) return 1;
    int prev = powerOf2(n / 2);
    int curr = prev * 2;
    return curr;
}
// 50: 25, 12, 6, 3, 1  --> O(logn)

O(log(10^n))

while (n > 0) {
    sum += n % 10;
    n /= 10; // n = 10^d
}

Complexity-Examples