Case 1: $O(N\log{N})$ and $O(N^2)$

Quicksort

1
2
3
4
5
quicksort(num, lo, hi) {
  p = partition(num, lo, hi)  // O(hi - lo)
  quicksort(num, lo, p);
  quicksort(num, p + 1, hi);
}

The complexity is dependent on whether the partition halves the data.

  • Time:
    • Best: $T(N) = 2T(N/2) + O(N) = O(N\log{N})$
    • Worst: $T(N) = T(N - 1) + T(1) + O(N) = O(N^2)$
    • Non-worst: $T(N) = T(N/10) + T(9N/10) + O(N) = O(N\log{N})$
  • Space:
    • Best: $O(\log{N})$
    • Worst: $O(N)$

Mergesort

1
2
3
4
5
6
mergesort(num, lo, hi) {
  mid = lo + (hi - lo) / 2;
  mergesort(num, lo, mid);
  mergesort(num, mid + 1, hi)
  merge(num, lo, mid, hi) // O(hi - lo)
}
  • Time:
    • Best: $T(N) = 2T(N/2) + O(N) = O(N\log{N})$
    • Worst: $O(N\log{N})$ since the partition always halves the array.
  • Space:
    • $O(N) = O(\log{N} + N)$ since mergesort needs an auxiliary array.

Case 2: $O(\log{N})$ and $O(N)$

1
2
3
4
5
6
7
8
9
10
binarySearch(num, lo, hi) {
  mid = lo + (hi - lo) / 2;
  if (some condition) {
    binarySearch(num, lo, mid);
  } else if (some condition) {
    binarySearch(num, mid + 1, hi);
  } else {
    return num[mid];
  }
}
  • Time: $T(N) = T(N/2) + O(1) = O(\log{N})$
  • Space: $O(\log{N})$

Binary Tree Traversal

1
2
3
4
5
inorder(root) {
  inorder(root.left);
  print(root.val);      // visit - O(1)
  inorder(root.right);
}
  • Time:
    • Best: $T(N) = 2T(N/2) + O(1) = O(N)$ if the tree is perfect or bushy.
    • Worst: $T(N) = T(N - 1) + T(1) + O(1) = O(N)$ if the tree is spindly.
    • Note: Notice that the runtimes are the same.
  • Space:
    • Best: $O(\log{N})$ if the tree is perfect or bushy.
    • Worst: $O(N)$ if the tree is spindly.
  • Variant:
    • If the visiting part takes more than $O(1)$, say $O(N)$, the runtime would be similar to Quicksort, which depends on the partition. And $O(N)$ is the total amount of work at each level (please imagine the situation in a binary tree).

Case 3: $O(2^N)$ and $O(N!)$

Combination

  • $N$ is the total job size
  • Initially, call: combination(0, 0)
  • For each depth, call combination() for $N$ times.
1
2
3
4
5
6
7
8
combination(depth, start) {
  if (depth == N) {
    return ...
  }
  for (int i = start; i < N; ++i) { // the work size keep decreasing
    combination(depth + 1, i);
  }
}
  • Time: $T(N) = T(N - 1) + T(N - 2) + \ldots + T(1) = O(2^N)$
  • Space: $O(N)$

Permutation

1
2
3
4
5
6
7
8
9
10
11
permutation(depth, used) {
  if (depth == N) {
    return ...
  }
  for (int i : 0...N) { // the workload does not change
    if (i in used) continue;
    used.add(i);
    permutation(depth + 1, used);
    used.remove(i);
  }
}
  • Time: $T(N) = N * T(N -1) = O(N!)$
  • Space: $O(N)$

Case 4: DP

Fibonacci

1
2
3
4
fib(n) {
  if (n < 1) return 1;
  return fib(n - 1) + fib(n - 2);
}
  • Time: $T(N) = T(N - 1) + T(N - 2) + O(1) = O(2^N) = O(1.618^N)$
  • Space: $O(N)$

Fibonacci with DP

1
2
3
4
5
6
fib(n) {
  if (n < 1) return 1;
  if (m[n] > 0) return m[n];
  m[n] = fib(n - 1) + fib(n - 2);
  return m[n];
}
  • Time:
    • Number of subproblems $N$ $\times$ Exclusive time to solve each subproblem $O(1)$
    • $T(N) = O(N)$
  • Space:
    • Max depth of call stack $\times$ Space used by each subproblem
    • $O(N)$

More to go when you work on DP problems